最大XOR值比仅使用XOR更快

Question

给定一个数字N和一个整数数组(所有的nos都小于2^15)。(A是数组100000的大小)

从数组中查找最大XOR值N和整数。

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

输入：

阿Q

a1 a2 a3 .

N启动停止

输出：

指定范围的数组中N和整数的最大XOR值。

输入

15 2 (2不属于查询)

1 2 3 4 5 6 7 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，a1，.，a15，例如，如果N= 13 = 0000000 00001101 (二进制)，那么a= a1 =.a11 = 0，a12 = 1，a13 = 1，a14 = 0，a15 = 1。

算法的主要思想是:如果一个== 1，那么最好的答案是这个位零。如果是== 0，那么最佳可能的答案就是这个位置的答案。因此，一开始，您检查是否有一些数字与所需的位。如果是，你应该只取这个位的数字。如果不是，你就认为它是相反的。然后以相同的方式处理其他比特。例如，如果== 1，a1 == 0，您首先检查是否有以零开头的数字，如果是，则检查是否有以01开头的数字。如果没有从零开始，那么你就会检查是否有一个数字和11在一起。等等……

因此，您需要一个快速算法来回答以下查询:是否有以位开头的数字.在射程内开始，停止？

一种可能性: Constuct从数字的二进制表示开始。在每个节点中存储此前缀位于数组中的所有位置(并对它们进行排序)。然后，回答这个查询可以简单地遍历这个trie。要检查start中是否有合适的前缀，应对节点中存储的数组执行二进制搜索。

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

下面是代码，它没有经过太多的测试，可能包含bug：

#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);
  }
}

Answer 2

如果有具有相同范围的多个查询，则可以构建一个包含该范围内数字的树，如下所示：

使用深度为15的二叉树，其中数字在叶子处，一个数字对应于通向它的路径(左为0，右为1)。

例如0 1 4 7：

    /   \
  /      /\
/ \     /  \
0 1    4    7

那么查询是N=n_1 n_2 n_3…吗？n_15，n_1是N的第一个位，n_2是第二个…从根转到叶，当您必须选择如果n_i =0(其中我是当前节点的深度)，然后转到右边，否则转到左边。当你在叶子上的时候，它就是最大的叶子。

一个问题的原始答案：

您的算法是最优的，您需要检查数组中的所有数字。

也许有一种方法可以通过使用编程技巧来获得一个稍微快一点的程序，但是它与算法没有联系。

Answer 3

您的算法以线性时间运行(O(start-stop)，或全范围的O(N) )。如果不能假设输入数组已经有了特殊的排序，那么您可能无法更快地得到它。

您只能尝试优化循环中的开销，但这肯定不会显著提高速度。

编辑：

看起来，您必须多次搜索相同的列表，但使用不同的开始和结束索引。

这意味着预先排序数组也是不可能的，因为这将改变元素的顺序。start和end将毫无意义。

如果一个查询完全包含已扫描的范围，您可以尝试避免两次处理相同的范围。

或者在迭代数组时尝试同时考虑所有查询。