最大XOR值比仅使用XOR更快

Question

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

Q不是查询(50000)并且start,stop是数组中的范围.

输入:
AQ
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倍的算法.排序太贵了.我也尝试过二叉树,位操作.

2x - 3x的改进怎么样？这是可能的优化.

Answer 1

可以开发更快的算法.

让我们调用N的位:a [0],a [1],...,a [15],例如,如果N = 13 = 0000000 00001101(二进制),则a [0] = a [1] =. .. [11] = 0,a [12] = 1,a [13] = 1,a [14] = 0,a [15] = 1.

算法的主要思想如下:如果[0] == 1,则最佳可能的答案将此位置零.如果[0] == 0,则最佳答案在此位置有一个答案.所以首先你要检查你是否有一个带有所需位的数字.如果是,您应该只使用此位数.如果不是,你就把它反过来.然后以相同的方式处理其他位.例如,如果[0] == 1,a [1] == 0,首先检查是否有以零开头的数字,如果是,则检查是否有以01开头的数字.如果没有以零开头,则你检查是否有一个数字与11开始等等...等等...

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

一种可能性:从数字的二进制表示构造trie.在每个节点中存储此前缀在数组中的所有位置(并对它们进行排序).然后回答这个问题可以简单地通过这个trie.要检查start,stop范围中是否有合适的前缀,您应该对节点中存储的数组进行二进制搜索.

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