Segment Tree XOR Query

XOR on ranges is associative with identity 0—segment tree works; combine with ^ instead of +.

Why this shows up in the real world

Time-series dashboards, game leaderboards, and competitive programming interval problems all need fast answers on changing arrays.

Core idea (explained for students)

Useful for parity tricks, subset XOR on intervals, and pairing with lazy XOR tags later.

Try this in Python

class SegTreeXor:
    def __init__(self, arr: list[int]) -> None:
        self.n = len(arr)
        self.size = 1
        while self.size < self.n:
            self.size *= 2
        self.t = [0] * (2 * self.size)
        for i, x in enumerate(arr):
            self.t[self.size + i] = x
        for i in range(self.size - 1, 0, -1):
            self.t[i] = self.t[2 * i] ^ self.t[2 * i + 1]

    def query(self, l: int, r: int) -> int:
        l += self.size
        r += self.size
        x = 0
        while l <= r:
            if l % 2 == 1:
                x ^= self.t[l]
                l += 1
            if r % 2 == 0:
                x ^= self.t[r]
                r -= 1
            l //= 2
            r //= 2
        return x


print(SegTreeXor([1, 2, 3, 4]).query(0, 3))

Common mistakes

• Confusing XOR lazy tags with addition lazy tags (different push rules).
• Integer overflow not an issue for XOR but wrong combine op is.

Key takeaways

• XOR is its own inverse: applying twice cancels—great for toggling.
• Try small bitmask arrays before big ints.