981. Counting Pairs Whose XOR Lands In a Range

Given n values and two bounds low and high, count the pairs of different positions whose XOR is at least low and at most high.

1 4 2 7, [2, 6] -> 6 every pair lands inside 7 7 7, [0, 0] -> 3 1 2 4 8, [1, 15] -> 6 1 2 3 4, [5, 5] -> 2

## One counter, used twice

Problem 980 counts the pairs whose XOR is strictly BELOW a limit. Write that as below(t). Then

answer = below(high + 1) - below(low)

because "at least low and at most high" is "below high + 1" minus "below low". Nothing new has to be invented; the whole problem is noticing that a two-sided question is a difference of one-sided ones, which is the same move that turns a range sum into a difference of prefix sums.

## The two details that break it

high + 1 can be 1073741824, which is 2^30 and therefore one past everything a 30 bit walk can represent. The counter must answer that case directly, as n (n - 1) / 2, before it starts descending. Letting the walk run on a 31 bit limit inside a 30 level trie silently drops the top bit and undercounts.

low = 0 must give below(0) = 0 rather than anything else, since no XOR is negative. That is the other early exit, and the pair of them is what makes the subtraction safe at both ends.

## Why the trie is built once and queried twice

The trie depends only on the values, not on the bound, so build it once and run the summation of problem 980 twice with different limits. Rebuilding it is not wrong, only wasteful: it doubles the 30 n insertions for no reason.

## Why each count uses the same halving

Each call sums countLess(x, t) over every value, which counts each real pair twice and each value against itself once, so each call subtracts n and halves before returning. Doing the subtraction once on the DIFFERENCE instead is wrong in general, because the two calls have different self counts when low is 0: below(0) counts nothing at all, self pairs included.

## Overflow, computed

Both intermediate counts and the answer need 64 bits. At n = 100000 a single call can return

100000 * 99999 / 2 = 4999950000

which is about 2.3 times 2147483647, and the raw sum before halving is close to 10^10. The values themselves stay below 2^30 and are comfortable in 32 bits.

## Cost

Building is O(30 n) and each of the two counts is O(30 n), so about 9 million steps at the limits. Space is at most 1 + 30 n = 3000001 nodes.

Constraints - `1 ≤ n ≤ 100000` - `0 ≤ each value ≤ 1073741823`, which is `2^30 - 1` - `0 ≤ low ≤ high ≤ 1073741823` - Values may repeat.