Range XOR bases: merge linear spans in a segment tree

Last updated: 5 Oct 20269 min read

tutorial

A linear XOR basis stores independent bit vectors whose combinations span the same XOR results as its input values. Each nonzero vector is reduced from its highest set bit downward; an unoccupied pivot becomes a new basis vector, while an occupied pivot is XORed away. A segment tree stores such a basis for every array interval. Joining two nodes inserts every right basis pivot into a copy of the left basis, preserving the span of all values in their union. A half-open range query merges the O(log N) nodes covering that range, then greedily raises the answer by XORing pivots from high bit to low bit. The same range basis can test whether a target XOR is representable and report its linear rank. This model uses fixed-width unsigned shipment flags, supports point replacement, and treats duplicate values as separate inputs that may be linearly dependent.

Operational case

For flags [47,29,61,83,19], the range [1,4) covers 29, 61, and 83. Its maximum subset XOR is 115, and the three values are independent at the configured width. The target 29 XOR 61 is representable because those two items may be selected. Replacing 61 with 37 changes the range maximum to 118; the empty range [4,4) contains only the empty subset, whose XOR is zero. A basis describes achievable XOR values, not which shipment IDs produce them. A user needing the witness subset would have to retain provenance through elimination, which this compact model does not do.

Working Python program

class XorBasis:
    def __init__(self, width=12):
        self.width = width
        self.pivots = [0] * width

    def add(self, value):
        if not 0 <= value < 1 << self.width:
            raise ValueError("value outside the configured bit width")
        for bit in range(self.width - 1, -1, -1):
            if not value & (1 << bit):
                continue
            if self.pivots[bit]:
                value ^= self.pivots[bit]
            else:
                self.pivots[bit] = value
                return

    def absorb(self, other):
        for pivot in other.pivots:
            if pivot:
                self.add(pivot)

    def maximum(self):
        result = 0
        for pivot in reversed(self.pivots):
            result = max(result, result ^ pivot)
        return result

    def can_make(self, target):
        if not 0 <= target < 1 << self.width:
            return False
        for bit in range(self.width - 1, -1, -1):
            if target & (1 << bit):
                if not self.pivots[bit]:
                    return False
                target ^= self.pivots[bit]
        return True

    def rank(self):
        return sum(bool(pivot) for pivot in self.pivots)


class RangeXorBasis:
    def __init__(self, shipment_flags, width=12):
        self.width = width
        self.length = len(shipment_flags)
        self.leaves = 1 << (max(1, self.length) - 1).bit_length()
        self.tree = [XorBasis(width) for _ in range(self.leaves * 2)]
        for position, flags in enumerate(shipment_flags):
            self.tree[self.leaves + position].add(flags)
        for position in range(self.leaves - 1, 0, -1):
            self.tree[position].absorb(self.tree[position * 2])
            self.tree[position].absorb(self.tree[position * 2 + 1])

    def replace(self, position, flags):
        if not 0 <= position < self.length:
            raise IndexError("position outside shipment list")
        position += self.leaves
        self.tree[position] = XorBasis(self.width)
        self.tree[position].add(flags)
        position //= 2
        while position:
            self.tree[position] = XorBasis(self.width)
            self.tree[position].absorb(self.tree[position * 2])
            self.tree[position].absorb(self.tree[position * 2 + 1])
            position //= 2

    def basis(self, start, stop):
        if not 0 <= start <= stop <= self.length:
            raise IndexError("query must be a valid half-open range")
        answer = XorBasis(self.width)
        start += self.leaves
        stop += self.leaves
        while start < stop:
            if start & 1:
                answer.absorb(self.tree[start])
                start += 1
            if stop & 1:
                stop -= 1
                answer.absorb(self.tree[stop])
            start //= 2
            stop //= 2
        return answer


if __name__ == "__main__":
    index = RangeXorBasis([47, 29, 61, 83, 19])
    selected = index.basis(1, 4)
    print(selected.maximum(), selected.rank(), selected.can_make(29 ^ 61))
    index.replace(2, 37)
    print(index.basis(1, 4).maximum(), index.basis(4, 4).maximum())

Output

115 3 True
118 0

Time, space, and tradeoff

Let B be the configured bit width. Inserting one value into a basis takes O(B) bit tests and XORs. Merging two bases may insert up to B pivots and costs O(B squared), giving O(N B squared) segment-tree construction time and O(NB) stored pivot cells. A range query visits O(log N) covering nodes and costs O(B squared log N), followed by O(B) for maximum or reachability. Point replacement rebuilds O(log N) ancestors at the same merge cost. B is twelve in the runnable program, so Python integers fit comfortably, but the stated bound keeps bit width explicit. A binary trie answers maximum XOR against one chosen query value; a range linear basis answers the maximum XOR of any subset in an interval.

Common Mistakes

Do not confuse maximum subset XOR with maximum XOR against one element.
Do not count dependent duplicate vectors as extra rank.
Do not reuse a parent basis after one leaf changes.
Do not accept flags outside the fixed bit width.

Connected lessons

Compare this operation boundary with Persistent range MEX: search last occurrences in prefix versions, Affine lazy segment trees: compose range calibration before summing, Min-max heaps: remove either end of one dispatch priority array, then complete the audit project and decision quiz.

data structures

range-query-structures