algorithm - 最大 XOR 值比仅使用 XOR 更快

Question

给定一个数字 N 和一个整数数组(所有整数都小于 2^15)。 (A 是数组 100000 的大小)
从数组中找到 N 和整数的最大 XOR 值。

Q是查询次数(50000)和开始，停止是数组中的范围。

输入:
问
a1 a2 a3 ...
N 开始停止

输出:
N的最大XOR值与数组中指定范围内的整数。

例如:输入
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)

输出:
13
13

代码:

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 倍的改进怎么样？。是否可以通过优化实现。

Answer 1

有可能开发出更快的算法。

让我们调用 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，则最佳可能答案在此位置有一个。所以首先你检查你是否有一些具有所需位的数字。如果是，你应该只用这个位取数字。如果不是，则取反。然后您以相同的方式处理其他位。例如。 if a[0] == 1, a[1] == 0，首先检查是否有以0开头的数字，如果有则检查是否有以01开头的数字。如果没有以0开头的数字，那么你检查是否有11开头的数字，以此类推...

所以你需要一个快速的算法来回答以下查询:是否有一个以位开头的数字...在范围开始，停止？

一种可能性:从数字的二进制表示构造 trie。在每个节点中存储此前缀在数组中的所有位置(并对它们进行排序)。然后回答这个查询可以简单地遍历这个 trie。要检查开始、结束范围内是否有合适的前缀，您应该对节点中存储的数组进行二分查找。

这可能导致复杂度为 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);
  }
}