28.05Intermediate / Advanced5 topics15 min2 interactive animations

Bitwise tries

A trie over the bits of integers answers maximum-XOR questions greedily: at each bit, try to go to the opposite bit.

Learning goals

Store integers as paths of bits in a binary trie
Find the maximum XOR of two array elements in O(n × bits)
Reduce subarray XOR questions to pair questions with prefix XORs
Choose the bit length and support online insert, delete and query

Prerequisites

Bit manipulationPrefix XORTrie fundamentals

To make a XOR large you want a 1 in the highest possible bit, so you look for a partner that differs from you there. A binary trie finds such a partner one bit at a time without trying every pair.

28.05.1

XOR maximum pair

Maximum XOR of two array elements is naively O(n²). The greedy idea: XOR is largest when the highest bits differ, so for a fixed x choose, at each bit from the top, the child that is the opposite of x's bit when it exists. Insert the numbers into a binary trie (one edge per bit, high bit first) and query each number against the trie.

Is the greedy choice safe? A 1 in a higher bit is worth more than every lower bit together (2^b > 2^b - 1), so taking the opposite bit whenever possible can never lose. Run the preset "Max pair XOR" (3, 10, 5, 8, 2): the animation shows the opposite edges being chosen, and the best pair gives 15 (10 ^ 5 = 1010 ^ 0101).

Java

1class XorTrie {
2    private static final int B = 31;             // bits 30..0 cover every non-negative int
3    private final int[][] next;
4    private int size = 1;
5    XorTrie(int maxNodes) { next = new int[maxNodes * B + 1][2]; }
6    void insert(int x) {
7        int n = 0;
8        for (int b = B - 1; b >= 0; b--) {       // high bit first
9            int bit = (x >> b) & 1;
10            if (next[n][bit] == 0) next[n][bit] = size++;     // create the missing edge
11            n = next[n][bit];
12        }
13    }
14    int maxXor(int x) {                          // best partner among inserted values
15        int n = 0, best = 0;
16        for (int b = B - 1; b >= 0; b--) {
17            int bit = (x >> b) & 1;
18            int want = bit ^ 1;                  // the opposite bit puts a 1 in the result
19            if (next[n][want] != 0) { best |= 1 << b; n = next[n][want]; }
20            else n = next[n][bit];
21        }
22        return best;
23    }
24    static int maxPairXor(int[] a) {
25        XorTrie t = new XorTrie(a.length);
26        t.insert(a[0]);
27        int best = 0;
28        for (int i = 1; i < a.length; i++) { best = Math.max(best, t.maxXor(a[i])); t.insert(a[i]); }
29        return best;
30    }
31}

Binary trie: maximum XOR of a pair or of a subarray

Interactive · edit the input

binary trie (edge = next bit, high bit first) · 1 node

root

Greedy pathInserted pathBest partnerStored value

a[]

30011

101010

50101

81000

20010

Setup

To maximise a ^ b for a fixed a, pick the b that differs from a in the highest bits. A binary trie of the earlier values lets us choose the opposite bit at every level.

Step 1 / 27

Java

1void insert(int x) {
2    int n = 0;
3    for (int b = B - 1; b >= 0; b--) {                   // high bit first
4        int bit = (x >> b) & 1;
5        if (next[n][bit] == 0) next[n][bit] = size++;    // create the missing edge
6        n = next[n][bit];
7    }
8}
9int maxXor(int x) {                                      // best partner among inserted values
10    int n = 0, best = 0;
11    for (int b = B - 1; b >= 0; b--) {
12        int bit = (x >> b) & 1;
13        int want = bit ^ 1;                              // the opposite bit puts a 1 in the result
14        if (next[n][want] != 0) { best |= 1 << b; n = next[n][want]; }
15        else n = next[n][bit];
16    }
17    return best;
18}
19int maxPairXor(int[] a) {
20    XorTrie t = new XorTrie(); t.insert(a[0]); int best = 0;
21    for (int i = 1; i < a.length; i++) { best = Math.max(best, t.maxXor(a[i])); t.insert(a[i]); }
22    return best;
23}
24int maxSubarrayXor(int[] a) {
25    XorTrie t = new XorTrie(); t.insert(0); int p = 0, best = 0;   // prefix XOR starts at 0
26    for (int x : a) { p ^= x; best = Math.max(best, t.maxXor(p)); t.insert(p); }
27    return best;
28}

Live state

0 bit steps

best

No condition evaluated on this step

Execution trace (dry run table)Show 27 steps

Step	Line	State	What happens
1	L1	best=0	To maximise a ^ b for a fixed a, pick the b that differs from a in the highest bits. A binary trie of the earlier values lets us choose the opposite bit at every level.
2	L6	insert=3 bits=0011	Insert 3 = 0011: follow or create one edge per bit. Equal values share one path.
3	L14	x=10 bit=3 x bit=1 result so far=8	Bit 3 of 10 is 1; the opposite edge 0 exists, so the result gets a 1 here (1000).
4	L15	x=10 bit=2 x bit=0 result so far=8	Bit 2 of 10 is 0; no 1 edge exists, so the only way forward is 0 and the result bit stays 0.
5	L15	x=10 bit=1 x bit=1 result so far=8	Bit 1 of 10 is 1; no 0 edge exists, so the only way forward is 1 and the result bit stays 0.
6	L14	x=10 bit=0 x bit=0 result so far=9	Bit 0 of 10 is 0; the opposite edge 1 exists, so the result gets a 1 here (1001).
7	L21	x=10 max with earlier=9 best=9	Best partner for 10 among the earlier values gives 9. The best so far is 9.
8	L6	insert=10 bits=1010	Insert 10 = 1010: follow or create one edge per bit. Equal values share one path.
9	L14	x=5 bit=3 x bit=0 result so far=8	Bit 3 of 5 is 0; the opposite edge 1 exists, so the result gets a 1 here (1000).
10	L14	x=5 bit=2 x bit=1 result so far=12	Bit 2 of 5 is 1; the opposite edge 0 exists, so the result gets a 1 here (1100).
11	L14	x=5 bit=1 x bit=0 result so far=14	Bit 1 of 5 is 0; the opposite edge 1 exists, so the result gets a 1 here (1110).
12	L14	x=5 bit=0 x bit=1 result so far=15	Bit 0 of 5 is 1; the opposite edge 0 exists, so the result gets a 1 here (1111).
13	L21	x=5 max with earlier=15 best=15	Best partner for 5 among the earlier values gives 15. The best so far is 15.
14	L6	insert=5 bits=0101	Insert 5 = 0101: follow or create one edge per bit. Equal values share one path.
15	L14	x=8 bit=3 x bit=1 result so far=8	Bit 3 of 8 is 1; the opposite edge 0 exists, so the result gets a 1 here (1000).
16	L14	x=8 bit=2 x bit=0 result so far=12	Bit 2 of 8 is 0; the opposite edge 1 exists, so the result gets a 1 here (1100).
17	L15	x=8 bit=1 x bit=0 result so far=12	Bit 1 of 8 is 0; no 1 edge exists, so the only way forward is 0 and the result bit stays 0.
18	L14	x=8 bit=0 x bit=0 result so far=13	Bit 0 of 8 is 0; the opposite edge 1 exists, so the result gets a 1 here (1101).
19	L21	x=8 max with earlier=13 best=15	Best partner for 8 among the earlier values gives 13. The best so far is 15.
20	L6	insert=8 bits=1000	Insert 8 = 1000: follow or create one edge per bit. Equal values share one path.
21	L14	x=2 bit=3 x bit=0 result so far=8	Bit 3 of 2 is 0; the opposite edge 1 exists, so the result gets a 1 here (1000).
22	L15	x=2 bit=2 x bit=0 result so far=8	Bit 2 of 2 is 0; no 1 edge exists, so the only way forward is 0 and the result bit stays 0.
23	L14	x=2 bit=1 x bit=1 result so far=10	Bit 1 of 2 is 1; the opposite edge 0 exists, so the result gets a 1 here (1010).
24	L15	x=2 bit=0 x bit=0 result so far=10	Bit 0 of 2 is 0; no 1 edge exists, so the only way forward is 0 and the result bit stays 0.
25	L21	x=2 max with earlier=10 best=15	Best partner for 2 among the earlier values gives 10. The best so far is 15.
26	L6	insert=2 bits=0010	Insert 2 = 0010: follow or create one edge per bit. Equal values share one path.
27	L22	return=15 bit steps=16	Maximum pair XOR = 15. Each value costs 4 bit steps for the query and 4 to insert: O(n · bits), independent of the values' size otherwise.

28.05.2

XOR subarrays

The XOR of a subarray a[l..r] is p[r + 1] ^ p[l], where p is the prefix XOR array with p[0] = 0 (the same idea as prefix sums). So the maximum subarray XOR is the maximum XOR over pairs of prefix values. Start the trie with p[0] = 0, then for each prefix query the trie and insert it.

Pick the preset "Max subarray XOR" (8, 1, 2, 12, 7): the prefixes are 0, 8, 9, 11, 7, 0, and the animation's second row shows them next to the array. The same trie can also count subarrays whose XOR is below a limit K if every node stores a pass counter: at each bit where K has a 1, all values in the opposite-matching branch are smaller.

Java

1class XorCounter {
2    private static final int B = 31;
3    private final int[][] next;
4    private final int[] pass;                    // how many inserted values go through each node
5    private int size = 1;
6    XorCounter(int maxValues) { next = new int[maxValues * B + 1][2]; pass = new int[maxValues * B + 1]; }
7    void insert(int x) {
8        int n = 0;
9        for (int b = B - 1; b >= 0; b--) {
10            int bit = (x >> b) & 1;
11            if (next[n][bit] == 0) next[n][bit] = size++;
12            n = next[n][bit];
13            pass[n]++;
14        }
15    }
16    int maxXor(int x) {
17        int n = 0, best = 0;
18        for (int b = B - 1; b >= 0; b--) {
19            int bit = (x >> b) & 1;
20            if (next[n][bit ^ 1] != 0) { best |= 1 << b; n = next[n][bit ^ 1]; }
21            else n = next[n][bit];
22        }
23        return best;
24    }
25    long countLess(int x, int limit) {           // inserted values y with (x ^ y) < limit
26        int n = 0;
27        long count = 0;
28        for (int b = B - 1; b >= 0 && n != -1; b--) {
29            int xb = (x >> b) & 1, lb = (limit >> b) & 1;
30            if (lb == 1) {
31                int same = next[n][xb];          // x ^ y has a 0 here: strictly below the limit, whatever follows
32                if (same != 0) count += pass[same];
33                int other = next[n][xb ^ 1];     // x ^ y has a 1 here: still tied with the limit
34                n = other != 0 ? other : -1;
35            } else {
36                int same = next[n][xb];          // must keep the XOR bit 0 to stay below the limit
37                n = same != 0 ? same : -1;
38            }
39        }
40        return count;
41    }
42    static int maxSubarrayXor(int[] a) {
43        XorCounter t = new XorCounter(a.length + 1);
44        t.insert(0);
45        int p = 0, best = 0;
46        for (int x : a) { p ^= x; best = Math.max(best, t.maxXor(p)); t.insert(p); }
47        return best;
48    }
49    static long countSubarraysXorLess(int[] a, int limit) {
50        XorCounter t = new XorCounter(a.length + 1);
51        t.insert(0);
52        int p = 0;
53        long total = 0;
54        for (int x : a) { p ^= x; total += t.countLess(p, limit); t.insert(p); }
55        return total;
56    }
57}

Binary trie: maximum XOR of a pair or of a subarray

Interactive · edit the input

binary trie (edge = next bit, high bit first) · 1 node

root

Greedy pathInserted pathBest partnerStored value

a[]

30011

101010

50101

81000

20010

Setup

To maximise a ^ b for a fixed a, pick the b that differs from a in the highest bits. A binary trie of the earlier values lets us choose the opposite bit at every level.

Step 1 / 27

Java

1void insert(int x) {
2    int n = 0;
3    for (int b = B - 1; b >= 0; b--) {                   // high bit first
4        int bit = (x >> b) & 1;
5        if (next[n][bit] == 0) next[n][bit] = size++;    // create the missing edge
6        n = next[n][bit];
7    }
8}
9int maxXor(int x) {                                      // best partner among inserted values
10    int n = 0, best = 0;
11    for (int b = B - 1; b >= 0; b--) {
12        int bit = (x >> b) & 1;
13        int want = bit ^ 1;                              // the opposite bit puts a 1 in the result
14        if (next[n][want] != 0) { best |= 1 << b; n = next[n][want]; }
15        else n = next[n][bit];
16    }
17    return best;
18}
19int maxPairXor(int[] a) {
20    XorTrie t = new XorTrie(); t.insert(a[0]); int best = 0;
21    for (int i = 1; i < a.length; i++) { best = Math.max(best, t.maxXor(a[i])); t.insert(a[i]); }
22    return best;
23}
24int maxSubarrayXor(int[] a) {
25    XorTrie t = new XorTrie(); t.insert(0); int p = 0, best = 0;   // prefix XOR starts at 0
26    for (int x : a) { p ^= x; best = Math.max(best, t.maxXor(p)); t.insert(p); }
27    return best;
28}

Live state

0 bit steps

best

No condition evaluated on this step

Execution trace (dry run table)Show 27 steps

Step	Line	State	What happens
1	L1	best=0	To maximise a ^ b for a fixed a, pick the b that differs from a in the highest bits. A binary trie of the earlier values lets us choose the opposite bit at every level.
2	L6	insert=3 bits=0011	Insert 3 = 0011: follow or create one edge per bit. Equal values share one path.
3	L14	x=10 bit=3 x bit=1 result so far=8	Bit 3 of 10 is 1; the opposite edge 0 exists, so the result gets a 1 here (1000).
4	L15	x=10 bit=2 x bit=0 result so far=8	Bit 2 of 10 is 0; no 1 edge exists, so the only way forward is 0 and the result bit stays 0.
5	L15	x=10 bit=1 x bit=1 result so far=8	Bit 1 of 10 is 1; no 0 edge exists, so the only way forward is 1 and the result bit stays 0.
6	L14	x=10 bit=0 x bit=0 result so far=9	Bit 0 of 10 is 0; the opposite edge 1 exists, so the result gets a 1 here (1001).
7	L21	x=10 max with earlier=9 best=9	Best partner for 10 among the earlier values gives 9. The best so far is 9.
8	L6	insert=10 bits=1010	Insert 10 = 1010: follow or create one edge per bit. Equal values share one path.
9	L14	x=5 bit=3 x bit=0 result so far=8	Bit 3 of 5 is 0; the opposite edge 1 exists, so the result gets a 1 here (1000).
10	L14	x=5 bit=2 x bit=1 result so far=12	Bit 2 of 5 is 1; the opposite edge 0 exists, so the result gets a 1 here (1100).
11	L14	x=5 bit=1 x bit=0 result so far=14	Bit 1 of 5 is 0; the opposite edge 1 exists, so the result gets a 1 here (1110).
12	L14	x=5 bit=0 x bit=1 result so far=15	Bit 0 of 5 is 1; the opposite edge 0 exists, so the result gets a 1 here (1111).
13	L21	x=5 max with earlier=15 best=15	Best partner for 5 among the earlier values gives 15. The best so far is 15.
14	L6	insert=5 bits=0101	Insert 5 = 0101: follow or create one edge per bit. Equal values share one path.
15	L14	x=8 bit=3 x bit=1 result so far=8	Bit 3 of 8 is 1; the opposite edge 0 exists, so the result gets a 1 here (1000).
16	L14	x=8 bit=2 x bit=0 result so far=12	Bit 2 of 8 is 0; the opposite edge 1 exists, so the result gets a 1 here (1100).
17	L15	x=8 bit=1 x bit=0 result so far=12	Bit 1 of 8 is 0; no 1 edge exists, so the only way forward is 0 and the result bit stays 0.
18	L14	x=8 bit=0 x bit=0 result so far=13	Bit 0 of 8 is 0; the opposite edge 1 exists, so the result gets a 1 here (1101).
19	L21	x=8 max with earlier=13 best=15	Best partner for 8 among the earlier values gives 13. The best so far is 15.
20	L6	insert=8 bits=1000	Insert 8 = 1000: follow or create one edge per bit. Equal values share one path.
21	L14	x=2 bit=3 x bit=0 result so far=8	Bit 3 of 2 is 0; the opposite edge 1 exists, so the result gets a 1 here (1000).
22	L15	x=2 bit=2 x bit=0 result so far=8	Bit 2 of 2 is 0; no 1 edge exists, so the only way forward is 0 and the result bit stays 0.
23	L14	x=2 bit=1 x bit=1 result so far=10	Bit 1 of 2 is 1; the opposite edge 0 exists, so the result gets a 1 here (1010).
24	L15	x=2 bit=0 x bit=0 result so far=10	Bit 0 of 2 is 0; no 1 edge exists, so the only way forward is 0 and the result bit stays 0.
25	L21	x=2 max with earlier=10 best=15	Best partner for 2 among the earlier values gives 10. The best so far is 15.
26	L6	insert=2 bits=0010	Insert 2 = 0010: follow or create one edge per bit. Equal values share one path.
27	L22	return=15 bit steps=16	Maximum pair XOR = 15. Each value costs 4 bit steps for the query and 4 to insert: O(n · bits), independent of the values' size otherwise.

28.05.3

Binary integers

A binary trie reads an integer's bits from the most significant down. For 32-bit ints the bit at position b is (x >> b) & 1. All keys must be read with the same number of bits, so shorter numbers are padded with leading zeros; otherwise the paths of different numbers would not line up.

Negative numbers are a trap: in two's complement the sign bit (bit 31) is 1, so negative values sort after positives and a XOR of a positive with a negative is negative. Either restrict the problem to non-negative values (as most XOR problems do) and read 31 bits, or add an offset to make all values non-negative before inserting.

Value	4-bit path (high to low)	Reads
3	0 0 1 1	(3 >> 3) & 1 = 0, then 0, 1, 1
10	1 0 1 0	(10 >> 3) & 1 = 1, then 0, 1, 0
10 ^ 5	1 1 1 1	1010 ^ 0101 = 1111 = 15

Java

1static int bit(int x, int b) { return (x >> b) & 1; }       // bit b of x, 0 = least significant
2static String bits(int x, int width) {                      // x as `width` bits, high bit first
3    StringBuilder sb = new StringBuilder();
4    for (int b = width - 1; b >= 0; b--) sb.append(bit(x, b));
5    return sb.toString();
6}

28.05.4

Bit length

The depth of the trie is the number of bits, and every operation costs that many steps. Do not always use 32: if the largest value needs only 10 bits, 10 levels are enough and the trie is three times smaller and faster. The number of bits needed for a non-negative max is 32 - Integer.numberOfLeadingZeros(max), with a minimum of 1 for the value 0.

If the values are below 2^B, every node in the trie has depth at most B, so the node count is at most n × B + 1. The maximum XOR of two such values is also below 2^B, so int never overflows. Pick B from the data once, before building the trie.

Java

1static int bitsNeeded(int max) {                 // bits needed to write any value in 0..max
2    return max == 0 ? 1 : 32 - Integer.numberOfLeadingZeros(max);
3}
4static int bitsNeeded(int[] a) {
5    int max = 0;
6    for (int x : a) max = Math.max(max, x);
7    return bitsNeeded(max);
8}

28.05.5

Online XOR queries

In an online version, values arrive and leave over time and queries are interleaved: add x, remove x, ask for the maximum XOR of y with the current set. Keep a pass counter on every node. Insert increments the counters along the path, removal decrements them, and a query treats an edge as present only while the counter of its child is positive.

This works with duplicates too: two copies of x raise the counters twice, and one removal still leaves the path alive. Each operation costs O(bits), independent of the number of values stored. The trie never frees nodes in this version; with many distinct values being added and removed, the node pool can be recycled when a counter reaches zero.

Java

1class OnlineXor {
2    private static final int B = 31;
3    private final int[][] next;
4    private final int[] pass;
5    private int size = 1;
6    OnlineXor(int maxInserts) { next = new int[maxInserts * B + 1][2]; pass = new int[maxInserts * B + 1]; }
7    void add(int x) {
8        int n = 0;
9        for (int b = B - 1; b >= 0; b--) {
10            int bit = (x >> b) & 1;
11            if (next[n][bit] == 0) next[n][bit] = size++;
12            n = next[n][bit];
13            pass[n]++;
14        }
15    }
16    void remove(int x) {                         // x must be present
17        int n = 0;
18        for (int b = B - 1; b >= 0; b--) {
19            n = next[n][(x >> b) & 1];
20            pass[n]--;
21        }
22    }
23    int maxXor(int x) {                          // the set must not be empty
24        int n = 0, best = 0;
25        for (int b = B - 1; b >= 0; b--) {
26            int bit = (x >> b) & 1;
27            int want = next[n][bit ^ 1];
28            if (want != 0 && pass[want] > 0) { best |= 1 << b; n = want; }
29            else n = next[n][bit];
30        }
31        return best;
32    }
33}

Practice ladder

Now try it yourself

Easy

Single Number
Find the Difference

Medium

Maximum XOR of Two Numbers in an Array
Count Pairs With XOR in a Range

Advanced

Maximum XOR With an Element From Array
Maximum Genetic Difference Query

Key takeaways

A binary trie stores integers as bit paths, high bit first; every operation costs the number of bits.
For a maximum XOR, prefer the opposite bit at every level: a higher 1 outweighs all lower bits.
Subarray XOR = prefix XOR ^ prefix XOR, so subarray problems become pair problems; counters on nodes support deletion and counting.