（Trie）5696. 统计异或值在范围内的数对有多少

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

最大异或值，字典树

query求的是，左边异或值 < hi 的有多少个数

nums[i] (已经插入树中) xor nums[j] < hi

int u = (x >> i) & 1, h = (hi >> i) & 1;

• u=0, h=1时候
  往son[p][0]的这些数肯定都小于hi，加上
  往son[p][1]走
• u=1, h=1时候
  往son[p][1]的这些数肯定都小于hi，加上
  往son[p][0]走
• u=0, h=0时候
  往son[p][1]肯定是大于hi的
  往son[p][0]走
• u=1, h=0时候
  往son[p][0]肯定是大于hi的
  往son[p][1]走

const int N = 2010 * 30;

class Solution {
public:
    int son[N][2], idx = 0;
    int cnt[N];

    void insert(int x) {
        int p = 0;
        for (int i = 30; i >= 0; i--) {
            int u = (x >> i) & 1;
            if (!son[p][u])son[p][u] = ++idx;
            p = son[p][u];
            cnt[p]++;
        }
    }

    int query(int x, int hi) {
        int res = 0;
        int p = 0;
        for (int i = 30; i >= 0; i--) {
            int u = (x >> i) & 1, h = (hi >> i) & 1;
            if (u == 0 && h == 1) {
                res += cnt[son[p][0]];
                p = son[p][1];
            } else if (u == 1 && h == 1) {
                res += cnt[son[p][1]];
                p = son[p][0];
            } else if (u == 0 && h == 0) {
                p = son[p][0];
            } else if (u == 1 && h == 0) {
                p = son[p][1];
            }
            if (!p)return res;
        }
        return res;
    }

    int countPairs(vector<int> &nums, int low, int high) {
        for (auto i:nums)insert(i);
        int res = 0;
        for (auto i:nums) {
            res += query(i, high + 1) - query(i, low);
        }
        return res / 2;
    }
};