这道题实在太太太难了😭，我为大佬们写注解，都能写到快升天｜1803 题. 统计异或值在范围内的数对有多少｜liberg、灵佬、官方的三种解法 - 讨论

这道题实在太太太难了😭，我为大佬们写注解，都能写到快升天｜1803 题. 统计异或值在范...

老宋🐾

4523

2023.01.10

2023.01.11

发布于未知归属地

字典树哈希表计数前缀和 Java 剪枝异或位算法二进制技术交流暴力前缀树

老宋每日题解

题目：1803. 统计异或值在范围内的数对有多少

这是前几天（2023/01/05）的每日一题，这道题对现在的我，实在是太太太难了。这也是有生以来，从学前班到大学，从大学到工作，第一次难到让我怀疑人生、怀疑自己智商的一道题。有扣友评价它：

今日大敌当头，百思不得其解。——扣友@joey91

然后默默啃了官解和多位大佬的题解，想总结一下，结果因为太难，连总结都写了好几天。

这篇帖子耗费了我大量的心血，如果对你有用，可以点个赞再走🤣

「@liberg」大佬的暴力解法优化
「@灵佬」的解法
力扣官解
总结

「@liberg」大佬的暴力解法优化

原版代码

@liberg 大佬的题解：《Java暴力侥幸通过(1650 ms)》。

注意，这位大佬用的语言是Java，用其他小伙伴刷题的小伙伴，其思路仅做参考。


public int countPairs(int[] nums, int low, int high) {
    int ans = 0;
    int max = 0;
    int min = Integer.MAX_VALUE;
    int[] freq = new int[20001];
    for (int num : nums) {
        freq[num]++;
        max = Math.max(max, num);
        min = Math.min(min, num);
    }

    for (int j = min; j <= max; j++) {
        if(freq[j] == 0)continue;
        for (int i = low; i <= high; i++) {
            int xor = i ^ j;
            if(xor >=1 && xor <=20000) {
                ans += freq[j]*freq[xor];
            }
        }
    }
    return ans>>1;
}

思路解析和学习

我永远想不到这个思路，虽然并不难理解🤣：

首先遍历一遍数组，统计每个数字的频率（计数），并求出数组最大值和最小值。
然后利用一个双层循环，统计所有异或结果满足题意的数对的数量。这个双循环还利用了异或的性质：如果 $x \oplus y = z$ , 则 $x \oplus z = y$ ， $y \oplus z = x$ ，进行了边界优化。其中的 $\oplus$ 代表异或。
根据对称性，将第上一步得出的结果除以2。（大佬用右移符号完成的除 2：ans>>1）。

可以看到，大佬的优化思路，核心要义是剪枝：

一方面，将遍历每个下标，替换为只遍历可能的数字。数字的值是可重复的，可能性不会超过数组的长度，故这样减少了遍历次数。
另一方面，巧妙地利用了异或的性质，将内层循环的遍历范围限制在区间 $[l o w, hi g h]$ 内部，进一步减少了遍历次数。这就是我和大佬的差距之一，我反正是不知道这个性质的，但是大佬知道。

最坏情况下，剪枝可能不起作用，但是考虑到测试用例有一定的随机性，这个策略是有效的。除非，出题人比较“变态”，精心设计过用例🤣。

「@liberg」的代码魔改 1

事实上，即便不知道前面提到的异或性质，仅仅利用计数进行剪枝，本题也能 AC 的，而且执行时间甚至还更好：

/**
执行用时：1482 ms, 在所有 Java 提交中击败了18.28%的用户
内存消耗：43.3 M, 在所有 Java 提交中击败了98.07%的用户
通过测试用例：63 / 63
 */
class Solution {
    public int countPairs(int[] nums, int low, int high) {
        int ans = 0;
        int max = 0;
        int min = Integer.MAX_VALUE;
        int[] freq = new int[20001];
        for (int num : nums) {
            freq[num]++;
            max = Math.max(max, num);
            min = Math.min(min, num);
        }

        for (int j = min; j <= max; j++) {
            if(freq[j] == 0)continue;
            for (int i = j + 1; i <= max; i++) { // 相等的数字异或，必然等于 0，小于 low，所以 i 初始化为 j+1
                int xor = i ^ j;
                if(xor >= low && xor <= high) {
                    ans += freq[j] * freq[i];
                }
            }
        }
        return ans; // 结果不用除 2 了。
    }
}

「@liberg」的代码魔改 2

通常情况下，在使用哈希表的环境中，如果键的取值范围是确定的，那么用数组代替哈希表，可以取得更优的效果。尽管数组的下标是连续的，而哈希表的键不需要连续，所以数组中可能存在很多不必要的“窟窿”，浪费空间和遍历时间；但是，数组更加底层，而哈希表经过了更多的封装，根据我的经验，数组效果确实更好。

「@liberg」的解法中，也采取了这一策略。

但我依然好奇心大发，想着大佬在计数时，用的是一个长度为 20001 的数组，假如我换成哈希表，可以真正地减少循环的次数，省去大佬代码中对频率为 0 的数进行的 continue，还可以降低空间复杂度：

class Solution {
    public int countPairs(int[] nums, int low, int high) {
        int n = nums.length, ret = 0;
        Map<Integer, Integer> frq = new HashMap<>();
        for(int num: nums)frq.put(num, frq.getOrDefault(num, 0) + 1);
        for(int x: frq.keySet()){
            for(int t = low; t <= high; t++){
                int y = t ^ x;
                ret += frq.get(x) * frq.getOrDefault(y, 0);
            }
        }
        return ret / 2;
    }
}

然后，没有然后，喜提超时了。所以，键范围确定的情况下，尽量用数组替代哈希表吧。

「@灵佬」的解法

灵佬的原版代码

这道题的官解，对我来说看的很痛苦。首先需要我去学习之间没接触过过的字典树（也叫前缀树） 。

但是，当我补充了前缀树的知识，我依然……呃……那个……，读不懂官解🙃，相信我，我真的读了一遍又一遍，最后觉得我是个智障。所以@灵佬的解法让我抓住了救命稻草：

@灵佬的题解：《不会字典树？只用哈希表也能做！（Python/Java/C++/Go》

这标题，我打 100 分🤣。这帖子简直就是为我这种智商量身打造的嘛。

但我读了两遍，很快就哭着出来了，灵佬他固然没有骗我，但胜似骗我😭。对照着代码和文字反复看到三更半夜，才明白是怎么回事。

/**
作者：endlesscheng
链接：https://leetcode.cn/problems/count-pairs-with-xor-in-a-range/solution/bu-hui-zi-dian-shu-zhi-yong-ha-xi-biao-y-p2pu/

执行用时：70 ms, 在所有 Java 提交中击败了91.03%的用户
内存消耗：45 MB, 在所有 Java 提交中击败了76.07%的用户
通过测试用例：63 / 63
*/
class Solution {
    public int countPairs(int[] nums, int low, int high) {
        int ans = 0;
        var cnt = new HashMap<Integer, Integer>();
        for (int x : nums) cnt.put(x, cnt.getOrDefault(x, 0) + 1);
        for (++high; high > 0; high >>= 1, low >>= 1) {
            var nxt = new HashMap<Integer, Integer>();
            for (var e : cnt.entrySet()) {
                int x = e.getKey(), c = e.getValue();
                if ((high & 1) == 1) ans += c * cnt.getOrDefault(x ^ (high - 1), 0);
                if ((low & 1) == 1)  ans -= c * cnt.getOrDefault(x ^ (low - 1), 0);
                nxt.put(x >> 1, nxt.getOrDefault(x >> 1, 0) + c);
            }
            cnt = nxt;
        }
        return ans / 2;
    }
}

先恶补下位运算

以前每次看到官解用位运算，总觉得像是读鬼故事。我现在不害怕位运算了，但是位运算依旧每次都会给我新的惊喜（or 惊吓）。

问题一：考虑把一个非负整数 $x$ 转换为二进制形式，我起初唯一能想到的方法是：对一个数除以二，余数是最低位的二进制值，然后拿商继续除以二，余数是次低位二进制值，如此往复，直到商变成 0。这个法子的时间复杂度是 $l o g (n)$ 。

问题二：如果我想获取某个数的倒数第 n 位二进制值，我唯一能想到的法子是：先尝试把这个数转换成二进制，直到求出倒数第 i 位。如此，时间复杂度是是 O(n)。

但是用右移运算、按位与运算，可以更好地解决上面两个问题。

对于问题一，可以不断把 $x$ 右移一位，然后和 1 进行按位与运算，直到 $x = 0$ 。这样就能得到从低位到高位二进制序列了。这样做，比反复除以 2 效率高。

对于问题二，更是可以通过左移和按位与直接在 $O (1)$ 内解决：x & (1 << n)，如果等于 $0$ ，那么 $x$ 的倒数第 $n$ 位就是 $0$ ；否则为 1。

灵佬上面的代码里，就用了这种技巧。

感兴趣的小伙伴可以尝试一下这道题剑指 Offer II 003. 前 n 个数字二进制中 1 的个数，感受一下不同写法的差异，还挺有趣的：

/**
方法 1：反复除以 2。效率较差。
执行用时：7 ms, 在所有 Java 提交中击败了13.23%的用户
内存消耗：45.7 MB, 在所有 Java 提交中击败了30.92%的用户
通过测试用例：15 / 15
**/
class Solution {
    public int[] countBits(int n) {
        int[] ret = new int[n + 1];
        for(int i = 0; i <= n; i++){
            int v = i;
            while(v > 0){
                ret[i] += v % 2;
                v /= 2;
            }
        }
        return ret;
    }
}

/**
方法二：反复右移，效率较高
执行用时：2 ms, 在所有 Java 提交中击败了40.61%的用户
内存消耗：45.4 MB, 在所有 Java 提交中击败63.19%的用户
通过测试用例 15 / 15
 */
class Solution {
    public int[] countBits(int n) {
        int[] ret = new int[n + 1];
        for(int i = 0; i <= n; i++){
            int v = i;
            while(v > 0){
                ret[i] += v & 1;
                v >>= 1;
            }
        }
        return ret;
    }
}

此外，还可以尝试一下剑指 Offer 15. 二进制中1的个数，也十分有趣，可以用多种不同写法。

灵佬 java 代码中的奇特写法

我在灵佬的 java 版代码里看到了关键字 var，恍惚了一秒钟，还以为是 javascript 和 java 写串了（我是前端出身）。然后很快反应过来，这应该是 java8 以上的某个版本中新语法，我平常用的都是 java8 🤣。

还有就是，灵佬代码里那个 for 循环，看起来很奇特，我是第一次遇到：

// 第二个分号后的表达式子里，出现了逗号，而且居然不会报错，神奇
for (++high; high > 0; high >>= 1, low >>= 1){}

但java 里如果写成：

int i = 0, j = 0;
i = 10, j = 20;

那么第二行的逗号那里是会报错了。所以我对这个 for 循环里的逗号语法，感觉颇为奇特，学到了。

思路解析和学习【本节是重头戏🔑🏆👍】

灵佬的这个题解，技能点密度对我来说太高，所以前面铺垫的有点多了。现在正式开始给大佬做注解。这里再贴一遍灵佬的帖子链接，方便读者可以右键在浏览器新标签中打开，和本文对照着看：

@灵佬的题解：《不会字典树？只用哈希表也能做！（Python/Java/C++/Go》

下面基截自灵佬帖子的图中，我用红框圈出来的部分，其实就是我前面讲到的：[「@liberg」的代码魔改 2](#「「@liberg」的代码魔改 2)，所以这一块我们可以愉快地跳过，忘了的小伙伴点击蓝字跳到前面再看看：

接下来，把求解闭区间 $[l o w, hi g h]$ 上的数量问题，转换成分别求解求解左闭右开区间 $[0, hi g h + 1)$ 和 $[0, l o w)$ 上的数量问题，二者相减就是答案。这一步转换很要，这里利用了类似前缀和的思路：

对一个数组 arr，求出每一个下标对应的数组前缀中所有元素的和，就可以轻松求出任何一个下标区间内所有元素的和。

这也是我和大佬的差距，我虽然知道前缀和，也做过相关的题，但是这道题这么明显，也是要求解某个区间上的特定数量问题，我居然没有第一时间想起前缀和来。以后一定把这个观念焊死在脑子里。

原贴中下面这张图里被我描红的部分，真的是折磨了我好久好久，我连躺在床上睡觉了也依然在琢磨：

原贴中，即便灵佬还解释了一下：

问：「数对异或值的后两个比特是什么都可以」是什么意思？
答：区间 $[10000, 10011]$ 的后两个比特为 $00, 01, 10, 11$ ，无论是哪两个数异或，后面两个比特必然是这四种之一，所以只需要考虑 $nums [i]$ 的前三个比特就行了，后面两个比特是多少无所谓。

但这个解释对我依然是天书。真的需要感叹一句，造化钟神秀，但是把神秀都放在别人大脑里了，一点也没匀出来给我，绝望😭😭。这种绝望感有人能理解吗？

好在我锲而不舍，反复对比文字、代码、评论区的留言，总算看懂了。我现在尝试更形式化地为灵佬注解一下：

设数组 nums 中元素的二进制形式最长为 $ma x_bi t s$ 位，不足 $ma x_bi t s$ 位的数，前面补 $0$ 。遍历数组，分别统计长度为 $l = 0, 1, 2, \dots, ma x_bi t s$ 的所有可能的二进制前缀的数目。

对于一个非负数 $u pp er$ ，我们的目标是求左闭右开区间 $[0, u pp er)$ 上，所有 nums 中异或值位于该区间内的数对的数量。

假设 $u pp er$ 二进制形式中有 $k$ 位是 $1$ ，设其中倒数第 $i$ 个 1 位于倒数第 $p os (i)$ 位 ~~；不失一般性，假设 $u pp er$ 的倒数第 $1$ bit 为 1，否则 $u pp er \leftarrow u pp er + 1$ 更新之~~。于是，可以按照这些等于 $1$ 的位，将左闭右开区间 $[0, u pp er)$ ，拆分成 $k$ 个，其中倒数第 $i (i < k)$ 个为：

注意这些区间也是左闭右开。上面这个区间是使用数学语言描述的，看起来比较可怕，但是换成程序语言，就很好理解：区间右边界是把 $u pp er$ 的后 $p os (i) - 1$ 个二进制位替换成 0，左边界类似，可以使用右移和左移快速求出区间。

这个区间有这样的性质：区间内的每个数，都有公共二进制前缀:
$co mm o n_p re f i x (i) = ⌊ u pp er / 2^{p os (i) - 1} ⌋ - 1$
且该前缀的长度为：
$r an g e_l e n (i) = ma x_bi t s - i - 1$

举个例子， $u pp er = 1010 1_{(2)}$ ，其中共有三个 $1$ ，总共可以被拆分为三个区间：

倒数第 $1$ 个区间为 $[1010 0_{(2)}, 1010 1_{(2)}) = [1010 0_{(2)}, 1010 0_{(2)}]$ ，区间内的数，前缀都等于 $1010 0_{(2)}$ ，前缀长度为 $ma x_bi t s - i - 1 = 5 - 1 - 1 = 5$ 。
倒数第 $1$ 个区间为 $[1000 0_{(2)}, 1010 0_{(2)}) = [1000 0_{(2)}, 1001 1_{(2)}]$ ，区间内的数，前缀都等于 $10 0_{(2)}$ ，前缀长度为 $ma x_bi t s - i - 1 = 5 - 3 - 1 = 3$ 。
倒数第 $1$ 个区间为 $[0000 0_{(2)}, 1000 0_{(2)}) = [0000 0_{(2)}, 01111 (2)]$ ，区间内的数，前缀都等于 $0_{(2)}$ ，前缀长度为 $ma x_bi t s - i - 1 = 5 - 5 - 1 = 1$ 。

我们前面已经统计出了任意长度的某个前缀的数目，所以对于倒数第 $i$ 个区间，很容易求出所有异或值等于 $co mm o n_p re f i x (i)$ ，且长度等于 $r an g e_l e n (i)$ 的所有前缀对的数目 $p ai r_co u n t (i)$ 。显然， $p ai r_co u n t (i)$ 恰好等于异或和位于该区间内的所有原始数组中的元素对的数目。

至此，前面那张灵佬的图中描红的部分，就得到了解释。

最后，累加每个区间上的 $p ai r_co u n t (i)$ ，就能得到最终答案：

\frac{1}{2} \cdot i = 1 \sum k p ai r_co u n t (i)

注意：求和后要除以二，因为异或运算满足交换律，且相同的两个数异或结果为 0，而题目要求的 $(i, j)$ 对需要满足 $i < j$ 。

这个算法，会不会重复计数或者有所遗漏呢？不会。因为拆分出来的每个子区间彼此是连续的，既没有空隙，也没有重叠。

思路理顺以后，就是是编码工作了。灵佬的原版代码十分高效紧凑，一开始理解起来有点难度。所以我先写了一个等价的、更啰嗦、更低效、但是更好理解的魔改版本:

灵佬代码魔改 1：更容易理解的版本

这个版本核心，在于 helper 函数，我加了详细的注释。读者可以先看这个版本，然后再把代码精简成灵佬的版本：

/**
灵佬原版代码魔改 1：等价的、更啰嗦、更低效、但是更好理解的版本
执行用时：321 ms, 在所有 Java 提交中击败了20.31%的用户
内存消耗：48.8 MB, 在所有 Java 提交中击败了44.68%的用户
通过测试用例：63 / 63
 */
class Solution {
    private final int MAX_BITS = 15; // nums中的数字，最多有 MAX_BITS 个二进制位

    public int countPairs(int[] nums, int low, int high) {
        return helper(nums, high + 1) - helper(nums, low);
    }

    /**
    * 对于区间[0, upper)， 求出所有异或运算结果等于区间内任意元素的所有数对的数量，数对中的数字，都位于数组 nums 内。
    * 注意区间是左闭右开的
     */
    private int helper(int[] nums, int upper){
        int ret = 0;
        // 1. 统计不同长度的所有可能的前缀数目
        // cnt[i]是一个哈希表，存储 nums 中的数字被去掉结尾的 i 个 二进制位后形成的所有可能的【二进制前缀】的数量，key 表示前缀，value 表示数量
        Map<Integer, Integer>[] cnt = new HashMap[MAX_BITS + 1];
        for(int i = 0; i <= MAX_BITS; i++){
            Map<Integer, Integer> cntMap = new HashMap<>();
            for(int x: nums){
                // 将 nums 中的数字 x，右移 i 位，相当于去掉了最末尾的 i 个 bit，得到 x 的长度为 MAX_BITS - i 的前缀
                int prefix =  x >> i; 
                cntMap.put(prefix, cntMap.getOrDefault(prefix, 0) + 1);
                cnt[i] = cntMap;
            }
        }


        // 02. 切分区间，并且遍历每个子区间。设任意子区间有相同的长度 l 的公共前缀 prefix，只需要求出所有异或结果等于 prefix、且长度等于 l 的前缀对的数量，就能确定异或值位于该子区间内所有原始数字对的数量。
        // 为了演示思路，下面的代码略啰嗦低效
        // 这个 for循环遍历 upper 的所有二进制位中，等于 1 的位，并以此计算区间分割点，切出一个区间
        for(int i = 0; i < MAX_BITS; i++){
            if((upper & (1 << i)) == 0){ // upper的倒数第 i + 1 位是 0，跳过，直到遇到 1
                continue;
            }

            Map<Integer, Integer> cntMap = cnt[i];
            // upper 右移 i 位，也就是去掉结尾的 i 比特，得到前缀 upper >> i，此时前缀的倒数第 1 bit，肯定是 1
            // 由于 helper 求的是左闭右开区间[0, upper)上的情况，所以将前缀减去 1，用 t 表示之
            // t 就是当前切出的区间内所有数字的公共前缀，前缀的长度为 MAX_BITS - i。
            int t = (upper >> i) - 1; 
            // 求出所有「长度为 MAX_BITS - i 的前缀」两两异或后，结果等于公共前缀 t 的【前缀对儿】的数目。 用 count 表示
            int count = 0; 

            for(int x: cntMap.keySet()){
                // 更新异或结果等于 t 的数对的数量
                // 注意 if 条件不要写成 if(upper & 1 != 0)
                count += cntMap.get(x) * cntMap.getOrDefault(x ^ t, 0);            
            }
            ret += count;
        }
        return  ret >> 1; // 因为异或运算满足交换律，结果要除以 2。刚体会到右移运算的妙处，忍不住用一把哈哈。
    }
}

灵佬代码魔改 2：优化魔改版本 1 的空间消耗和循环次数

这个版本执行时间大大减少，和版本 1 相比：

不是一次性求出所有长度的前缀的数量，而是用一个滚动的哈希表，只储存当前需要的长度。并且，不需要对每个前缀长度都遍历一遍 nums，循环次数更小。
逐步对 upper 右移一位，发现末尾为 1 时进行区间切割，而不是完整遍历[0, max_bits], 减少了迭代次数。

这个版本再优化一下，就可以得到灵佬的原版了：只需把 helper(cnt, high + 1) 和 helper(cnt, low)，合并到一个 for 循环中，避免额外多做的那一次计数。

/**
灵佬原版魔改版本 2：优化了空间复杂度，减少了循环的迭代次数。
和魔改版本 1 相比，主要差别在：
1. 不是一次性求出所有长度的前缀的数量，而是用一个滚动的哈希表，只储存当前需要的长度。并且，不需要对每个前缀长度都遍历一遍 `nums`，循环次数更小。
2. 反复右移 upper，而不是完整遍历[0, max_bits], 减少了迭代次数。
这个版本再优化一下，就可以得到灵佬的原版了：把 helper(cnt, high + 1)和 helper(cnt, low)，合并到一个 for 循环中，避免额外多做的那一次计数。
执行用时：114 ms, 在所有 Java 提交中击败了25.38%的用户
内存消耗：48.7 MB, 在所有 Java 提交中击败了49.49%的用户
通过测试用例：63 / 63
 */
class Solution {
    public int countPairs(int[] nums, int low, int high) {
        int n = nums.length, ret = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        for(int num: nums)cnt.put(num, cnt.getOrDefault(num, 0) + 1);
        return helper(cnt, high + 1) - helper(cnt, low);
    }

    /**
    * 对于区间[0, upper)， 求出所有异或运算结果等于区间内任意元素的所有数对的数量，数对可能的取值位于 cnt 的 keySet 中。
    * 注意区间是左闭右开的
     */
    private int helper(Map<Integer, Integer> cnt, int upper){
        int ret = 0;
        for(; upper > 0; upper >>= 1){ // 每次循环，都把 upper 的最末二进制位去掉
            Map<Integer, Integer> next = new HashMap<>();
            int t = upper - 1;
            for(int x: cnt.keySet()){
                int c = cnt.get(x), prefix = x >> 1;
                // 更新异或结果等于 t 的数对的数量
                // 注意 if 条件不要写成 if(upper & 1 != 0)
                if((upper & 1) == 1)ret += c * cnt.getOrDefault(x ^ t, 0);
                // 计算将 x 去掉最末二进制位后的前缀 prefix的数量
                next.put(prefix, next.getOrDefault(prefix, 0) + c);              
            }
            cnt = next;
        }
        return  ret >> 1; // 因为异或运算满足交换律，结果要除以 2。刚体会到右移运算的妙处，忍不住用一把哈哈。
    }
}

灵佬代码魔改 3：用数组替代哈希表优化性能

前文提到过，在键值范围确定的情况下，用数组替代哈希表，通常可以取得更好的效果。

本版本就是按照这个思路做的优化，和原版相比，执行时间确实大幅提升。

/**
灵佬原版魔改 3：用数组替代哈希表
执行用时：21 ms, 在所有 Java 提交中击败了99.53%的用户
内存消耗：42.8 MB, 在所有 Java 提交中击败了99.21%的用户
通过测试用例：63 / 63
 */
class Solution {

    private final int N = 20001; // nums中数字的最大二进制位数
    public int countPairs(int[] nums, int low, int high) {
        int n = nums.length, ret = 0;
        int[] cnt = new int[N];
        for(int num: nums)cnt[num]++;
        for(++high; high > 0; high >>= 1, low >>= 1){
            int[] next = new int[N];
            for(int x = 0; x < cnt.length; x++){
                int c = cnt[x];
                if(c == 0)continue;
                if((high & 1) == 1){
                    int y = x ^ (high - 1);
                    if(y < N)ret += c * cnt[y];
                }
                if((low & 1) == 1){
                    int y = x ^ (low - 1);
                    if(y <= N)ret -= c * cnt[y];
                }
                next[x >> 1] += c;              
            }
            cnt = next;
        }
        return ret >> 1;
    }
}

复杂度分析

对复杂度计算不感兴趣的读者可以先跳过。灵佬原贴写到：

首先， $U$ 指的的是数组 nums 中的的最大值。

问： $U \leq n$ 时，为什么说第一次循环是 $O (U)$ ?
答： $U \leq n$ ，所以最坏情况下，数组中最多 $U$ 个互异的数，那么第一次循环时，哈希表 cnt 长度最坏为 $U$ 。而哈希表需要被遍历一次，所以是 $O (U)$ 。
问： $U \leq n$ 时，为什么说第 $i$ 次循环是 $O (U / 2^{i - 1})$ ?
答：每次循环中，都会统计长度比上一轮小 $1$ 的每个可能前缀各自的数量，前缀长度减小 1，是通过将上一轮的每个前缀右移 1 位实现的，相当于把上一轮的所有前缀除以 2 并向下取整，新前缀的最大值为 $U /2$ ，所以新前缀种类最多为上一轮的一半，哈希表的长度最大为上一轮的一半。递归可得第 $i$ 次的情况。
问： $U > n$ 时，为什么说前面 $O (lo g (U / n))$ 次循环都是 $O (n)$ ?为什么其余加起来是 $O (n)$
答：第 $i$ 轮循环，新前缀的的最大值为 $U / 2^{i - 1}$ ，因为 $U > n$ ，所以 $U / 2^{i - 1}$ 依然可能大于 $n$ ，令 $U / 2^{i - 1} <= n$ ，可求得 $i$ 的边界值为 $lo g (U / n) + 1$ 。 $i$ 超过这个边界值前，前缀种类一直是 $n$ ；超过后，情况转换为类似 $U \leq n$ 的情况。得证。

力扣官解

前置知识：字典树（前缀树）

读这道题的官解，是我第一次接触到前缀树这种数据结构。感觉，amzaing……到底还有多少种树是我不知道的？

官解给出的前缀树参考题目「208. 实现 Trie (前缀树)」，也十分有趣，并且不难理解。顾名思义，字典树中保存着一本字典，其每个节点对应着一个字符串前缀，从根节点到这个节点的路径，就是这个前缀；如果节点的 isEnd 属性为 true，则相应的前缀同时还是一个单词。

根据我的理解，前缀树和普通树在存储结构上最大的区别，是前缀树的子节点被存储在一个哈希表中，查找某个节点的值已知的子节点，可以在 $O (1)$ 内完成，而不用遍历所有子节点。所以，如果要查找前缀树中是否存在某个长度为 $n$ 的前缀或字符串，需要 $O (n)$ 的时间。

我对 208 这道题写了一个题解，比较了一下字符串两种不同的存储方式，再次印证了前文提到的：

在键值范围确定的情况下，用数组替代哈希表，通常可以取得更好的效果。

假如为字典树的节点维护一个 sum 属性，用来表示有多少个单词共用节点对应的前缀，并且在插入节点时维护这个属性，那么，用这种形式解这道地狱题。本题中，单词的字符集为 ${0, 1}$ ，单词指的就是 nums 中的数字的二进制序列，这样的字典树叫做 01-trie。

官解思路解析和学习

先上官解链接：

统计异或值在范围内的数对有多少。

官解再次诠释了什么叫：我认识每一个字，但是我真的不知道是什么意思。这真的是我刷题以来最绝望的一次。

我再次反复比对官解的文字和代码，当我看懂以后，我尝试自己复述一遍这个思路，写个题解；然后我绝望地发现，自然语言真的太苍白了，似乎不管我怎么表达，都说不清楚。当我过了两天重新准备完成这个题解时，我甚至连千辛万苦看懂的思路，居然也被忘了😭。

以前总是忍不住吐槽官解，以后再也不好意思吐槽了。如果你懂这种凌乱的感觉，快来和我握个抓~

官解也是先利用前缀和，对问题进行了转换。这一点和灵神的思路是一样的，只不过灵神的区间是左闭右开，官解是左右都闭，这关系不大。让我们再次把前缀和焊死在大脑里：

题目想要求解有多少对数字的异或运算结果处于 $[low, high]$ 之间，为了方便求解，我们用 $f (x)$ 来表示有多少对数字的异或运算结果小于等于 $x$ ，这时问题变为求解 $f (high) - f (low - 1)$ 。

随后，官解的文字描述部分，以光速迈进了迷魂阵模式，不管怎么读，都读不懂、读不通，我前后反复读了不下 20 遍。特别是下图中红框里圈出来的部分，极其费解，如果孤立地看某些句子，我甚至会认为这些句子可能是错误的，比如字面箭头处的句子①：

读不懂文字，只能硬着头皮读代码，相互参照着看。可以看到，代码中先是从左到右遍历 nums，将元素逐个加入到一颗 01 字典树（01-trie）；每次加入一个元素，都要调用一次 get 方法，这个 get 方法正是官解的核心，也是上图中的大红框所描述的内容。

我详细地给 get 方法加了注释，看完注释，大体上就能明白上图红框里的意思了（如果不抠红框里字眼的话）：

官解详细加注释版代码【本节也是重头戏🏆🔑👍】

/**
官解添加详细注释版。官解的核心，是下面详细被注释了的 get 方法。
执行用时：85 ms, 在所有 Java 提交中击败了74.44%的用户
内存消耗：48.8 MB, 在所有 Java 提交中击败了41.93%的用户
通过测试用例：63 / 63
*/
class Solution {
    // 字典树的根节点
    private Trie root = null;
    // 最高位的二进制位编号为 14
    private static final int HIGH_BIT = 14;

    public int countPairs(int[] nums, int low, int high) {
        return f(nums, high) - f(nums, low - 1);
    }

    public int f(int[] nums, int x) {
        root = new Trie();
        int res = 0;
        for (int i = 1; i < nums.length; i++) {
            add(nums[i - 1]);
            res += get(nums[i], x);
        }
        return res;
    }

    /*将数字 num 加入 01-tree*/
    public void add(int num) {
        Trie cur = root;
        for (int k = HIGH_BIT; k >= 0; k--) {
            int bit = (num >> k) & 1;
            if (cur.son[bit] == null) {
                cur.son[bit] = new Trie();
            }
            cur = cur.son[bit];
            cur.sum++;
        }
    }

    /**
     * 官解的核心方法。传入数组 nums 中的一个数 num。本方法被调用时，数组中位于 num 之前的所有数字，都已经被添加到了 01-trie 中了。
     * 还要传入一个上界 x，最终返回 nums 中所有异或结果位于区间 [0, x] 的数对（y, num）的数量，其中 y 是数组 nums 中位于 num 前面的数。
     * 注意：代码注释中说的【位】，都是指二进制位。
     * @param num
     * @param x
     * @return
     */
    public int get(int num, int x) {
        // 注意，本注解中，凡是说到树的【倒数第 几 层】、【倒数第 几 位】，都是从 1 算起，而不是从 0 算起。官解在逻辑上所有的数字补齐了前导 0，但是位数的编码是从 0 开始的，最高位为 HIGH_BIT = 14。
        // 初始化 cur 为 01-trie 的根节点。此时，cur 位于 01-trie 的倒数第 HIGH_BIT + 2 层。注意，按照官解的写法，树总共有 HIGH_BIT + 2 层。
        // 这个算法的主体是一个循环，每循环一次，cur 在树中的层级就会下降 1 层。记某次迭代中 cur 所在的层级为倒数第（k + 1）层，则
        // cur 总是沿着这样的轨迹运动：若 cur 存在某个子节点（必然位于倒数第 k 层），子节点对应的位和 num 的倒数第 k 位异或后，等于 x 的倒数第 k 位，那么将 cur 更新为它的这个子节点。如果找不到这样的子节点，则循环结束。
        Trie cur = root;

        int sum = 0; // 答案
        for (int k = HIGH_BIT; k >= 0; k--) { // 从最高层开始，按层序访问 01-trie
            // 新的一轮迭代开始，此时 cur 位于倒数第 k + 2 层，其子节点 cur.son[0]和 cur.son[1]位于第 k + 1 层
            // 此时，记 cur 对应的前缀为 prefix，如果 num 的倒数第 k + 2, k + 3, ……, HIGH_BIT,HIGH_BIT + 1 位和 prefix 相异或，算法会保证这几位必然都会变成 0；

            // 获取数字 num 倒数第 k + 1 位的值 r。心里需要有个基本认知：cur.son[r]的值，此时必然等于 r，二者异或一下，结果为 0；cur.son[r ^ 1] 的值 和 r 异或一下，结果为 1。
            int r = (num >> k) & 1;

            // 判断 x 的 倒数第 k + 1 位是 1 还是 0。
            if (((x >> k) & 1) != 0) {
                if (cur.son[r] != null) {
                    // x 的 倒数第 k + 1 位是 1，而在倒数 k + 2（含）位到倒数第 HIGH_BITS + 1（含）的位上，cur 对应的前缀 和 num 异或的结果等于 x 的相应位；
                    // 另一方面，前面已经提到，位于第 k + 1位（层）的cur.son[r]的值，此时必然等于 r，二者异或一下，结果为 0，
                    // 所以，nums 中任何以cur.son[r]为前缀的数字，和 num 异或后，必然小于 x；
                    // 所以，将cur.son[r] 的 sum值，累加到答案中
                    sum += cur.son[r].sum; // 把以这个子节点对应的前缀为前缀的所有数字的数目，累加到答案中
                // 那么，nums 中，还有没有其他前缀不是 cur.son[r] 的数字，也满足条件呢？
                // 必然是有可能的，但是现在还没法确定这些数字，只能按照 cur 运动规则，让它继续沿着树往下走。怎么证明这个运动规则一定能帮助得到正确答案，既不会遗漏任何数字对，也不会重复计数呢？这一点需要证明，先按下不表。
                }
                
                // 此时，cur.son[r]无法满足 cur 的运动方向，而它的兄弟节点 cur.son[r ^ 1] 和 r 异或后等于 1，和 x 的第 k 位 1 必然相等，按照前面提到的 cur 的运动规则，将 cur 更新为 cur.son[r ^ 1]。如果cur.son[r ^ 1]不存在，循环结束。
                if (cur.son[r ^ 1] == null) {
                    return sum;
                }
                cur = cur.son[r ^ 1];


            } else {
                // x 的 倒数第 k + 1 位是 0。
                // 此时cur.son[r] 和 r 异或后，必然等于 0，而此时 x 的倒数第 k 位恰好也是 0， 按照前面提到的 cur 的运动规则，将 cur 更新为 cur.son[r]。如果cur.son[r] 不存在，循环终止。
                if (cur.son[r] == null) {
                    return sum;
                }
                cur = cur.son[r];
            }
        }

        // 能走到这一步，说明 cur 的运动轨迹恰好等于 x 。cur 此刻对应 x 的最后一位， cur 的 sum 值代表等于 x 的数字，cur 和 num 异或后，恰好等于 x，满足条件，将其 sum 累加到结果中。
        sum += cur.sum;
        return sum;
    }
}

class Trie {
    // son[0] 表示左子树，son[1] 表示右子树
    Trie[] son = new Trie[2];
    int sum;

    public Trie() {
        sum = 0;
    }
}

以上，是我写过的最狂乱的代码注释。我再也不想遇到第二次了。官解中的位的编号是倒着来的，而且从 $0$ 开始，真的让好难受。

看懂算法执行的流程后，新问题来了：正如注释中提到的，怎么证明这个算法既不会重复计数，也不会有遗漏呢？

官解正确性证明

现在我们已经搞清楚了官解的步骤，但是官解并没有给出正确性证明，或者官解以为它给出了，只是我没有看出来🦉。（现在说话好难，必须严谨一点，不然又被能被喷，说我态度有问题，是在怼官解）

容易注意到，官解中对结果有贡献的时刻，是 get 方法中发现上界 x 的某一位为 $1$ 的时候。此时，不妨设这个位是第 $i$ 位（从 $1$ 开始编号），则此时的 cur.son[r]，和 num 的前 $i$ 位异或后，得到的前缀为 x 的前 $i$ 位减去 $1$ 。

⌊ x / 2^{H I G H_B I T + 1 - i} ⌋ \cdot 2^{H I G H_B I T + 1 - i} - 1

是不是似曾相识？

巧得很，灵佬的方案中，也是以为 $1$ 的位为关键点，来切分数组的。

这种相似性，暗示着两种解法具有某种底层的联系。

举个例子，令 $x = 10010000100100 0_{(2)}$ ，其中共有 4 个位是 1，对应的前缀可参照线图红色部分：

可以看到，这些分界点，与前面介绍灵佬的解法时，是很像的。

可以很直观地看到，图中的 4 个红色的前缀，可以涵盖所有小于上界 $x$ 的数。由于官解中 $[0, x]$ 左右都是闭区间，所以循环结束后，还要额外加上异或值等于 $x$ 的数对的数量。如此，既不会重复计数，也不会遗漏。

有这个直观说明就够了，没必要再写一大堆公式形式化地证明了。我突然感觉打字好累啊🤣。

灵佬的解法和官解的关系

可以看到，等于 1 的位，在两种解法中都处于关键地位。

两种解法都利用了前缀，大大减少了暴力遍历的次数。

灵佬在他的题解里还提到了二者的不同：

其实这个方法就是字典树自底向上的过程，由于没有像字典树那样逐位统计 $nums [i]$ 的每个比特位，所以时间复杂度和空间复杂度都比字典树的写法要优（见复杂度分析）。

可以好好品味一下这段话。确实，官解是借助字典树，从高位到低位逐步计算的；灵佬的解法没有显示地声明字典树，是从低位到高位逐步计算的。

官解微调版：简洁度和性能优化

/**
官解优化：
1. 原先需要维护两颗字典树，改成 1 颗
2. 将区间右侧改成开区间，规避每次 get 方法中循环接结束后，需要额外在增加异或值等于 x 的数对数量
3. 简化 get 方法中漫山遍野的 if 条件

执行用时64 ms, 在所有 Java 提交中击败了95.49%的用户
内存消耗：49.1 MB, 在所有 Java 提交中击败了19.00%的用户
通过测试用例：63 / 63
 */
class Solution {
    class Trie {
        // son[0] 表示左子树，son[1] 表示右子树
        Trie[] son = new Trie[2];
        int sum;

        public Trie() {
            sum = 0;
        }
    }
    // 字典树的根节点
    private Trie root = null;
    // 最高位的二进制位编号为 14
    private static final int HIGH_BIT = 14;

    public int countPairs(int[] nums, int low, int high) {
        root = new Trie();
        int res = 0;
        high++;
        for (int i = 1; i < nums.length; i++) {
            add(nums[i - 1]);
            res += get(nums[i], high);
            res -= get(nums[i], low);
        }
        return res;
    }

    public void add(int num) {
        Trie cur = root;
        for (int k = HIGH_BIT; k >= 0; k--) {
            int bit = (num >> k) & 1;
            if (cur.son[bit] == null) {
                cur.son[bit] = new Trie();
            }
            cur = cur.son[bit];
            cur.sum++;
        }
    }

    public int get(int num, int x) {
        Trie cur = root;
        int sum = 0;
        for (int k = HIGH_BIT; k >= 0; k--) {
            int r = (num >> k) & 1;
            int rx = (x >> k) & 1;
            if(rx == 1 && cur.son[r] != null) sum += cur.son[r].sum;
            Trie next = cur.son[r ^ rx];
            if(next == null) return sum;
            cur = next;
        }
        return sum;
    }
}

总结

终于写完了，可以睡个好觉了。

技能点汇总

评估 leetcode 解法超时的边界数量级。
计数。
利用移位运算和按位与运算，求数字的任意一个二进制位。
异或运算的性质：如果 $x \oplus y = z$ , 则 $x \oplus z = y$ ， $y \oplus z = x$ 。在 Latex 语法中， $\oplus$ 代表了异或运算，可使用 \oplus 输出之，很形象也很好记， $+$ 外面套了个 $O$ 。
利用前缀和，将区间计数问题加以转换。
键值范围固定的情况下，用数组替代哈希表通常有更好的的效果。
滚动数组。
字典树数据结构。

为什么这道题如此磨人？

这道题消耗了我大量的时间，而且并不仅仅是因为缺乏字典树这个前置技能。我在学习了字典树后，依然在很长时间内，怎么都看不懂这道题的题解，无论是灵佬的，还是官解。

解决的办法，似乎只能是来回看文字和代码，一边靠文字猜测代码的逻辑，一边靠代码猜测文字的含义，相互印证🤣。但是这样效率奇低，这个过程中需要不断做出各种假设，并仔细求证，期间思维很容易发散，最后耗尽精力一无所获。

以后再遇到这种文字比较难懂的情况，我会选择把主要精力放在啃代码上。因为文字这种载体比较特殊，表达者传递的，和阅读者理解到的，可能相差会很远，特别是用自然语言表达的时候。而代码不同于文字，需要遵循硬一点的逻辑，写错了无法通过。

通过硬啃代码，至少可以先搞清楚算法的流程。光搞清楚流程，可能依然搞不清背后的原理，但是针对流程提出的疑问，可以为进一步思考提供目标和着力点。

此外，这两篇题解都侧重于描述算法本身，没有详细提供对正确性的证明，可能是大佬觉得比较简单，但是对我来说是巨大的门槛。

关于题解的写作风格

我有时候，自己也会写点题解，虽然主要是为了让自己看，但是毕竟是公开的，还是希望能逐渐提高写作水平，收到读者的认可。本题的两篇题解，让我对技术协作本身思考了很多。

不过这部分就略过了，不放在本文了🤣。

最后，创作不易，请留下你的赞再走^_^，这样小海豹会很开心的~~。