v. XOR Basis

Integers are vectors over ${\mathbb{F}}_2$ and XOR is vector addition. Any set of numbers spans a subspace of dimension $r\le B$ (the bit width), represented by a basis of at most $B$ numbers. Insertion is Gaussian elimination, one vector at a time.

Structure

struct XorBasis {
    static const int B = 60;
    ll b[B] = {}; int rank = 0;
    bool insert(ll x) {                         // true if x enlarged the span
        for (int i = B - 1; i >= 0 && x; i--) if (x >> i & 1) {
            if (!b[i]) { b[i] = x; rank++; return true; }
            x ^= b[i];
        }
        return false;
    }
    bool contains(ll x) const {
        for (int i = B - 1; i >= 0; i--) if (x >> i & 1) { if (!b[i]) return false; x ^= b[i]; }
        return true;
    }
    ll maxXor(ll x = 0) const { for (int i = B - 1; i >= 0; i--) x = max(x, x ^ b[i]); return x; }
    ll minXor(ll x) const { for (int i = B - 1; i >= 0; i--) x = min(x, x ^ b[i]); return x; }
};

b[i] has highest bit $i$ (row echelon form). Insertion and queries are $O(B)$.

Proof: insertion preserves the span, contains is correct, and maxXor is optimal

Span preservation. insert(x) only ever replaces x by x ^ b[i] (XORing by an existing basis vector, which doesn’t change the span since $b[i]$ is already in it) or adds the final nonzero remainder as a new basis vector with a pivot bit no other vector has. So at every point $\mathrm{span}(b)$ after inserting $x$ equals $\mathrm{span}(b\text{ before})\cup \{x\}$‘s span: either $x$ reduced to $0$ (already in the span) or the leftover is a genuinely new vector, linearly independent of the current basis because its leading bit $i$ is zero in every existing $b[j]$ ($j\ne i$, by the row-echelon invariant) and nonzero in itself, so it cannot be written as a combination of the others. By induction over insertions, b always spans exactly the same subspace as all inserted vectors, and rank counts the dimension. contains. Reducing $x$ against the basis top-down XORs out bit $i$ using $b[i]$ whenever $x$ has bit $i$ set; if that pivot is missing ($b[i]=0$), no combination of the basis (all of which are zero at bit $i$ or higher pivots only — row echelon) can cancel that bit, so $x\notin \mathrm{span}$. If every encountered bit has a pivot, $x$ reduces to exactly $0$, which happens iff $x$ is a linear combination of the basis vectors used, i.e. $x\in \mathrm{span}(b)$. maxXor. Greedily taking $x\oplus b[i]$ whenever it increases $x$, scanning pivots from the highest bit down: once a pivot’s bit is fixed to $1$ in the running answer (either because $x$ already had it, or XORing $b[i]$ sets it), no later (lower-pivot) operation can clear a higher bit, since every $b[j]$ for $j<i$ has all bits $\ge i$ equal to zero in row-echelon form below the point where $b[i]$‘s pivot sits (reduced form has distinct pivots, and the standard greedy variant used here, while not fully reduced, still never reintroduces a cleared higher bit, since later $b[j]$ have pivot $j<i$ so XORing them can only change bits $\le j<i$). So the greedy choice at each pivot is locally optimal and never sacrifices a higher bit for a lower one, which is exactly what maximizes the integer value bit by bit from the top. $■$

Tested against full $2^n$ subset-XOR enumeration for $n$ up to 7: span size $2^r$, contains matching exact reachability, every reachable value hit exactly $2^{n-r}$ times, and maxXor() matching the brute-force maximum — all confirmed.

What it answers

Question	Answer
maximum subset XOR (optionally XORed with $x$)	greedy from the top bit
minimum XOR of $x$ with an element of the span	greedy minimising
is $x$ a subset XOR?	reduce to 0
number of distinct subset XORs	$2^r$
number of subsets (of $n$ inputs) with XOR $=x$, for reachable $x$	$2^{n-r}$ (each value hit equally often, including the empty subset for $x=0$)
$k$-th smallest subset XOR	fully reduce, then read $k$ in binary
minimum non-zero subset XOR	smallest vector after full reduction (if $r<n$, then 0 is reachable non-trivially)
merge two bases	insert one into the other, $O(B^2)$
rank of a set over ${\mathbb{F}}_2$	rank

Full reduction: for each pivot $i$, clear bit $i$ from every other basis vector. Then the reduced vectors sorted by pivot are $v_0<v_1<\dots$, and the $k$-th smallest element of the span (0-indexed, counting 0) is ${⨁}_{j:k_j=1}{v}_j$.

Proof: $2^r$ distinct subset XORs, each hit by exactly $2^{n-r}$ subsets, and the $k$-th-smallest readout

Counting. The map $\phi :\{0,1{\}}^n\to {\mathbb{F}}_2^B$ sending a subset (as an indicator vector) to its XOR is ${\mathbb{F}}_2$-linear, and its image is exactly $\mathrm{span}(a_1,\dots ,a_n)$, which has dimension $r$ (the basis rank), so $|\mathrm{image}(\phi )|=2^r$ — that is the count of distinct subset XORs. By the rank-nullity theorem, $\ker \phi$ has dimension $n-r$, so $|\ker \phi |=2^{n-r}$; since $\phi$ is a group homomorphism from $({\mathbb{F}}_2^n,\oplus )$ to $({\mathbb{F}}_2^B,\oplus )$, every fiber ${\phi }^{-1}(x)$ for $x$ in the image is a coset of $\ker \phi$ (translate any one solution by every kernel element), hence has the same size $2^{n-r}$ — this is why reachable values are hit equally often, not just on average. $k$-th smallest. After full reduction, the $r$ basis vectors $v_0<v_1<\cdots <v_{r-1}$ (sorted by pivot, lowest first) have disjoint pivot bits with no vector sharing another’s pivot (by construction of full reduction), so the map $k\mapsto {⨁}_{j:k_j=1}{v}_j$ for $k\in [0,2^r)$ is injective (two different $k$ differ in some bit $j$, and $v_j$‘s pivot bit is only ever toggled by including $v_j$, since no other $v_{j^{\prime }}$ touches that bit after full reduction) and its image is exactly the span (every span element is some XOR-combination of the basis, and combinations correspond bijectively to subsets of the basis once the basis is linearly independent). Since XOR-combining more/fewer high-pivot vectors changes the result monotonically in the same direction as binary place value (the highest pivot included dominates all lower bits, by row-echelon structure), the combinations sorted by $k$‘s integer value are exactly the span sorted by integer value, so $k$‘s binary digits directly select the $k$-th smallest. $■$

Range and path queries

Prefix basis with timestamps (max subset XOR of $a[l..r]$ online): insert $a_r$ into the prefix-$r$ basis, keeping at each pivot the vector with the latest index (swap when the incoming index is newer, then continue reducing the older one). A query on $[l,r]$ uses only pivots with index $\ge l$. $O(nB)$ build, $O(B)$ per query, and it’s persistent (store one basis per prefix, $O(nB)$ memory).

ll b[B]; int pos[B];
void insert(ll x, int idx) {
    for (int i = B - 1; i >= 0; i--) if (x >> i & 1) {
        if (!b[i]) { b[i] = x; pos[i] = idx; return; }
        if (pos[i] < idx) swap(b[i], x), swap(pos[i], idx);
        x ^= b[i];
    }
}
// query [l, r] on the prefix-r snapshot: use b[i] only if pos[i] >= l

The same timestamp trick works on trees: the basis of the root-to-$v$ path keeps the deepest vectors, and a path query $u$–$v$ merges two such bases restricted to depth $\ge$ depth(LCA). Alternatives: segment tree of bases ($O(B^2\log n)$ per query), binary lifting, or offline divide and conquer.

Deletion: offline with a segment tree over time and an undo stack (record which b[i] was set). Online deletion of the most recently inserted element with the timestamp trick is also possible (“basis with deletion by time”).

Cycle space of a graph

Edge weights XORed around cycles form a linear space. Build a spanning tree with root XOR distances $d$; for each non-tree edge $(u,v,w)$ insert $d_u\oplus d_v\oplus w$. Then:

• the maximum XOR of a (not necessarily simple) path from $u$ to $v$ is maxXor(d[u] ^ d[v]);
• the minimum is minXor(d[u] ^ d[v]);
• the number of distinct path XOR values between $u$ and $v$ is $2^r$.

Walks may repeat edges, which is why every cycle can be added for free (go to the cycle, around it, and back).

Proof: the reachable path-XOR values from $u$ to $v$ are exactly $d_u\oplus d_v\oplus \mathrm{span}(\text{fundamental cycles})$

Fix a spanning tree with root distances $d$ (XOR of tree-edge weights from the root). Any walk from $u$ to $v$ can be decomposed into the tree path $u\to v$ (XOR value $d_u\oplus d_v$, since the tree path’s XOR telescopes to the two root-distances) composed with some number of detours, each of which walks from a vertex on the current path out to some edge and back. A detour using a non-tree edge $(p,q,w)$: walking tree-path to $p$, crossing $(p,q,w)$, then tree-path back from $q$ to the same point XORs in $d_p\oplus w\oplus d_q$ — exactly the fundamental cycle vector stored in the basis — because the tree-path portions from the detour’s start back to itself cancel (any edge traversed twice XORs to zero), leaving only the non-tree edge’s contribution combined with the root-distance difference it induces. Conversely, every basis vector (fundamental cycle) is realizable as such a detour, and detours compose by XOR (doing two detours back to back XORs their two cycle values, since the connecting tree-walk between them also cancels in pairs). So the set of all walk-XOR values from $u$ to $v$ is exactly $d_u\oplus d_v\oplus \mathrm{span}(\text{non-tree-edge cycle vectors})$, a coset of the cycle space — hence maxXor(d[u]^d[v]) and minXor(d[u]^d[v]) give the true max/min over all walks (not just simple paths), and the count of distinct values is $2^r$. $■$

Over other fields

The same row-echelon insertion works over ${\mathbb{F}}_p$ with vectors of dimension $d$ in $O(d^2)$ per insertion: normalise the pivot with an inverse and eliminate. The span has $p^r$ elements and every reachable vector has $p^{n-r}$ representations. Gaussian elimination in general is in Gaussian Elimination. Beyond ${\mathbb{F}}_2$‘s subset-XOR questions, the same machinery solves “is this modular linear system consistent, and how many solutions” and toggle puzzles like Lights Out (each move is a vector over ${\mathbb{F}}_2$, the reachable configurations are the span).

Matroid view

Linearly independent sets form a matroid. So “choose items maximising total weight such that their values are XOR-independent” is solved by sorting by weight and inserting greedily; the kept items are exactly those whose insertion enlarged the span — the same reason Kruskal’s algorithm is correct for spanning forests (a graphic matroid): both are “greedy is optimal for max-weight independent set in a matroid.”

Trie vs basis

“Choose a subset” means a basis; “choose one or two elements” means a binary trie (Binary Trie).

	XOR basis	Binary trie
Represents	the span of the set	the elements of the set
Max XOR over a subset	✔	✘
Max XOR with a single element	✘	✔
Count elements with a property	✘	✔
Deletion	hard (offline / timestamp trick above)	✔
Memory	$O(B)$	$O(nB)$
Merge two structures	$O(B^2)$	$O(nB)$