Daily LeetCode – day0160 1803. Count Pairs With XOR in a Range

// 1803. Count Pairs With XOR in a Range
class Solution {
    private Trie root;
    private static final int HIGH_BIT = 14;

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

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

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

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

class Trie {
    Trie[] son = new Trie[2];
    int belowSum;

    public Trie() {
        belowSum = 0;
    }
}

学习笔记：
这是一道超级困难题，用到了字典树，位运算。
我也看了解法后理解了思路，但是写不出来。后来看到了代码后跟着代码继续理解了两遍，把代码半默写了一遍。之后有时间还是要好好再研究研究这道题。