Advanced Binary Tries

May 2026 · 28 min read

Once you know maximum XOR, binary tries extend naturally to counting, range queries, deletions, and persistence. The key upgrade is storing counts at nodes so entire subtrees can be accepted or skipped during a query.

Count Values with x ^ y < K

Walk bits from high to low. If the current bit of K is 1, then choosing XOR bit 0 is safely below at this position, so add the whole matching subtree; then continue with XOR bit 1.

int count_less(int x, int k) {
    int u = 0, ans = 0;
    for (int b = LOG; b >= 0 && u != -1; --b) {
        int xb = (x >> b) & 1;
        int kb = (k >> b) & 1;
        if (kb) {
            int same = child[u][xb];
            if (same != -1) ans += cnt[same];
            u = child[u][xb ^ 1];
        } else {
            u = child[u][xb];
        }
    }
    return ans;
}

Persistent Trie for Range Queries

For prefix XOR array pref[i], build a persistent trie version after each prefix. A range query uses version r minus version l-1 counts to consider only prefixes in that interval.

// Each inserted value creates O(LOG) new nodes; unchanged children are shared.
int insert(int old, int x, int b) {
    int now = clone(old);
    cnt[now]++;
    if (b < 0) return now;
    int bit = (x >> b) & 1;
    child[now][bit] = insert(child[old][bit], x, b - 1);
    return now;
}

Minimum XOR Pair

The minimum XOR pair in a static array can be found by sorting, but a trie also supports online insertion. To minimize x ^ y, prefer the same bit first instead of the opposite bit.

Deletion and Multisets

Store counts along each path. Deleting decrements counts. Queries should ignore children with zero count.

Memory Tuning

• Use arrays or vectors of nodes, not new, for speed.
• Estimate nodes as (insertions * (LOG + 1)).
• Compress to 31 bits when inputs are non-negative int; use 63 for unsigned 64-bit.
• Persistent tries multiply memory by O(LOG) per update.

Practice Problems

• LeetCode 1803 - Count Pairs With XOR in a Range count less than K answer high+1 minus low.
• CSES - Maximum Xor Subarray prefix trie range-like prefix pairing.
• Codeforces 706D - Vasiliy's Multiset deletion dynamic trie multiset.
• SPOJ COT - Count on a Tree persistence idea persistent structures on paths.