Bitwise (0-1) Tries: Maximum XOR Subarray & Subtree Queries

1. MSB-to-LSB Greedy Dominance & Dynamic Deletion via cnt[u]

Why must a Bitwise Trie for XOR maximization or order-statistic comparison be rooted at the Most Significant Bit ($W - 1$) rather than bit $0$? Because binary value order is lexicographical from MSB to LSB: every number in the 1-branch at depth $k$ is strictly greater than every number in the 0-branch, since $2^k > 2^k - 1 = \sum_{j=0}^{k-1} 2^j$.

To support dynamic insert(x) and remove(x) (such as sliding-window XOR or multiset queries), we store an integer counter cnt[u] at every trie node recording how many active numbers pass through node $u$. Instead of physically freeing nodes on remove(x), we simply decrement cnt[u]-- along $x$'s path, and treat any child $c$ with c === 0 || cnt[c] === 0 as empty!

2. Production Implementation: Flat-Pool Bitwise Trie (insert, remove, maxXor, countXorLess, maxSubarrayXor)

/**
 * High-Performance 30-Bit Binary Trie using a Flat TypedArray Pool
 * Supports dynamic insert, remove, maxXor(x), and countXorLess(x, K) in O(W) time.
 */
class BitwiseTrie {
  constructor(maxInsertions = 100005, bitWidth = 30) {
    this.W = bitWidth;
    const maxNodes = maxInsertions * this.W + 2;
    this.ch = new Int32Array(maxNodes * 2); // ch[(u << 1) | bit]
    this.cnt = new Int32Array(maxNodes);
    this.ptr = 1; // Node 1 is root; Node 0 is null sentinel
  }

  insert(x, delta = 1) {
    let u = 1;
    this.cnt[u] += delta;
    for (let i = this.W - 1; i >= 0; i--) {
      const b = (x >>> i) & 1;
      const edgeIdx = (u << 1) | b;
      let next = this.ch[edgeIdx];
      if (next === 0) {
        next = ++this.ptr;
        this.ch[edgeIdx] = next;
      }
      u = next;
      this.cnt[u] += delta;
    }
  }

  remove(x) {
    this.insert(x, -1);
  }

  maxXor(x) {
    let u = 1;
    if (this.cnt[u] === 0) return 0;
    let ans = 0;
    for (let i = this.W - 1; i >= 0; i--) {
      const b = (x >>> i) & 1;
      const want = b ^ 1;
      const desiredChild = this.ch[(u << 1) | want];
      if (desiredChild !== 0 && this.cnt[desiredChild] > 0) {
        ans |= (1 << i);
        u = desiredChild;
      } else {
        u = this.ch[(u << 1) | b];
      }
    }
    return ans >>> 0;
  }

  /**
   * Returns count of active elements y in the trie such that (x ^ y) < k
   */
  countXorLess(x, k) {
    let u = 1;
    let total = 0;
    for (let i = this.W - 1; i >= 0 && u !== 0; i--) {
      const bx = (x >>> i) & 1;
      const bk = (k >>> i) & 1;
      if (bk === 1) {
        const sameChild = this.ch[(u << 1) | bx];
        if (sameChild !== 0) total += this.cnt[sameChild];
        u = this.ch[(u << 1) | (bx ^ 1)];
      } else {
        u = this.ch[(u << 1) | bx];
      }
    }
    return total;
  }
}

/**
 * Maximum XOR of any contiguous subarray A[L..R] in O(N * W) time
 */
function maxXorSubarray(arr, bitWidth = 30) {
  const trie = new BitwiseTrie(arr.length + 1, bitWidth);
  trie.insert(0); // Prefix XOR P[0] = 0 so subarrays starting at index 0 are included!
  let pref = 0;
  let best = 0;
  for (let i = 0; i < arr.length; i++) {
    pref ^= arr[i];
    best = Math.max(best, trie.maxXor(pref));
    trie.insert(pref);
  }
  return best;
}

3. Complexity Matrix