Every walkie-talkie at a festival is tuned to a non-negative integer channel. Two radios
crackle when the XOR of their channels lies between lo and hi inclusive. Given the list
channels (one entry per radio; several radios may share a channel), return the number of index
pairs (i, j) with i < j whose radios crackle.
Examples
Input: channels = [1, 4, 2, 7], lo = 2, hi = 5
Output: 4
Explanation: 1^4 = 5, 1^2 = 3, 4^7 = 3 and 2^7 = 5 are in range; 1^7 = 6 and 4^2 = 6 are not.
Input: channels = [3, 3, 3, 0], lo = 0, hi = 0
Output: 3
Explanation: a XOR of 0 means equal channels: the three radios on channel 3 form 3 pairs.
Constraints
0 <= len(channels) <= 2 * 10**40 <= channels[i] < 2**20,0 <= lo <= hi < 2**20- Target: about
O(n * 20); checking every pair isO(n**2)and too slow
Goals
- Count the stored values whose XOR with x is below a bound in one walk down a binary trie
- Add whole subtrees at once using counts kept on the nodes
- Turn a range [lo, hi] into two 'below' questions