最大 XOR 值比仅使用 XOR 更快

给定一个数字 N 和一个整数数组（均不小于 2^15）。 （A 是数组大小 100000）
从数组中查找 N 和整数的最大异或值。

Q 是查询数量 (50000)，start、stop 是数组中的范围。

Input:
A Q
a1 a2 a3 ...
N 启动停止

Output:
N 与数组中指定范围内的整数的最大异或值。

例如：输入
15 2（2 是查询数）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
10 6 10（查询1）
10 6 10（查询2）

Output:
13
13

Code:

for(int i=start-1;i<stop;i++){
int t =no[i]^a;
if(maxxor<t)
     maxxor=t;
}
cout << maxxor <<endl;

我需要一个比这个快 10-100 倍的算法。排序成本太高。我也尝试过二叉树、位操作。

2 倍 - 3 倍的改进怎么样？通过优化可以实现吗？

开发更快的算法是可能的。

我们将 N 的位称为：a[0]、a[1]、...、a[15]，例如，如果 N = 13 = 0000000 00001101（二进制），则 a[0] = a[1] = 。 ..a[11] = 0、a[12] = 1、a[13] = 1、a[14] = 0、a[15] = 1。

算法的主要思想如下：如果a[0] == 1，那么最好的可能答案就是将该位清零。如果 a[0] == 0，则最佳可能答案在该位置有 1。 因此，首先检查是否有一些具有所需位的数字。如果是，您应该只使用该位的数字。如果不是，则取其倒数。 然后以同样的方式处理其他位。例如。如果a[0] == 1, a[1] == 0，首先检查是否有以0开头的数字，如果有则检查是否有以01开头的数字。如果没有以0开头的数字，那么你检查是否有以11开头的数字。依此类推...

因此，您需要一个快速算法来回答以下查询：在开始、停止范围内是否存在以位...开头的数字？

一种可能性：从数字的二进制表示构造特里树。在每个节点中存储该前缀在数组中的所有位置（并对它们进行排序）。然后可以简单地浏览这个特里树来回答这个查询。要检查开始、停止范围中是否有合适的前缀，您应该对节点中存储的数组进行二分搜索。

这可能导致算法复杂度为 O(lg^2 N)，速度更快。

这是代码，尚未经过太多测试，可能包含错误：

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

class TrieNode {
 public:
  TrieNode* next[2];
  vector<int> positions;

  TrieNode() {
    next[0] = next[1] = NULL;
  }

  bool HasNumberInRange(int start, int stop) {
    vector<int>::iterator it = lower_bound(
        positions.begin(), positions.end(), start);
    if (it == positions.end()) return false;
    return *it < stop;
  }
};

void AddNumberToTrie(int number, int index, TrieNode* base) {
  TrieNode* cur = base;
  // Go through all binary digits from most significant
  for (int i = 14; i >= 0; i--) {
    int digit = 0;
    if ((number & (1 << i)) != 0) digit = 1;
    cur->positions.push_back(index);
    if (cur->next[digit] == NULL) {
      cur->next[digit] = new TrieNode;
    }
    cur = cur->next[digit];
  }
  cur->positions.push_back(index);
}

int FindBestNumber(int a, int start, int stop, TrieNode* base) {
  int best_num = 0;
  TrieNode* cur = base;
  for (int i = 14; i >= 0; i--) {
    int digit = 1;
    if ((a & (1 << i)) != 0) digit = 0;
    if (cur->next[digit] == NULL || 
        !cur->next[digit]->HasNumberInRange(start, stop))
      digit = 1 - digit;
    best_num *= 2;
    best_num += digit;
    cur = cur->next[digit];
  }
  return best_num;
}


int main() {
  int n; scanf("%d", &n);
  int q; scanf("%d", &q);
  TrieNode base;
  for (int i = 0; i < n; i++) {
    int x; scanf("%d", &x);
    AddNumberToTrie(x, i, &base);
  }

  for (int i = 0; i < q; i++) {
    int a, start, stop;
    // Finds biggest i, such that start <= i < stop and XOR with a is as big as possible
    // Base index is 0
    scanf("%d %d %d", &a, &start, &stop);
    printf("%d\n", FindBestNumber(a, start, stop, &base)^a);
  }
}