BIT for XOR Queries

BIT works for any invertible operation. XOR is self-inverse: $a \oplus a = 0$.

def queryXOR(i):
    result = 0
    while i > 0:
        result ^= tree[i]
        i -= i & (-i)
    return result

def updateXOR(i, val):
    while i <= n:
        tree[i] ^= val
        i += i & (-i)

Range XOR from $l$ to $r$: $\text{prefix}(r) \oplus \text{prefix}(l-1)$.

Use case: problems involving XOR of subarrays, toggling bits in ranges, or maintaining XOR over dynamic data.