如何从给定数组的范围查询中获取给定值和值的最小异或

Question

给定一个包含 n 个整数的数组 A 和范围 [l , r] 形式的查询和一个值 x，找到 A[i] XOR x 的最小值，其中 l <= i <= r 和 x对于不同的查询会有所不同。

我尝试使用线段树解决这个问题，但我不确定我应该在其中存储什么类型的信息，因为对于不同的查询，x 会有所不同。

0 < number of queries <= 1e4

0 < n <= 1e4

Answer 1

为了解决这个问题，我使用 std::vector 作为基础（不是数组，或 std::array），只是为了灵活性。

#include <algorithm>
#include <stdexcept>
#include <vector>

int get_xored_max(const std::vector<int>& values, const size_t l, const size_t r, const int xor_value)
{
    // check bounds of l and r
    if ((l >= values.size()) || (r >= values.size()))
    {
        throw std::invalid_argument("index out of bounds");
    }

    // todo check l < r

    // create left & right iterators to create a smaller vector 
    // only containing the subset we're interested in.
    auto left = values.begin() + l;
    auto right = values.begin() + r + 1;
    std::vector<int> range{ left, right };

    // xor all the values in the subset
    for (auto& v : range)
    {
        v ^= xor_value;
    }

    // use the standard library function for finding the iterator to the maximum
    // then use the * to dereference the iterator and get the value
    auto max_value = *std::max_element(range.begin(), range.end());
    return max_value;
}

int main()
{
    std::vector<int> values{ 1,3,5,4,2,4,7,9 };
    auto max_value = get_xored_max(values, 0u, 7u, 3);
    return 0;
}

Answer 2

方法-Trie+离线处理
时间复杂度 - O(N32)
Space 复杂度 - O(N32)

编辑：
这种方法会失败。我想，我们必须使用平方根分解而不是两个指针方法。

我已经使用 Trie 在 [l,r] 范围内找到最小异或来解决这个问题。我通过对查询进行排序来通过离线处理解决查询。

输入格式:
第一行有 n（元素数）和 q（查询数）。第二行包含数组的所有 n 个元素。每个后续行都有一个查询，每个查询有 3 个输入 l、r 和 x。

示例 -
输入-

首先，将所有 3 个查询转换为按 l 和 r 排序的查询。
转换后的查询 -

1 2 3
1 3 2
2 3 5

这里的关键是使用两个指针方法处理排序查询。

#include <bits/stdc++.h>
using namespace std;

const int N = (int)2e4 + 77;

int n, q, l, r, x;
int a[N], ans[N];
vector<pair<pair<int, int>, pair<int, int>>> queries;

// Trie Implementation starts
struct node
{
  int nxt[2], cnt;
  void newnode()
  {
    memset(nxt, 0, sizeof(nxt));
    cnt = 0;
  }
} trie[N * 32];
int tot = 1;

void update(int x, int v)
{
  int p = 1;
  for (int i = 31; i >= 0; i--)
  {
    int id = x >> i & 1;
    if (!trie[p].nxt[id])
    {
      trie[++tot].newnode();
      trie[p].nxt[id] = tot;
    }
    p = trie[p].nxt[id];
    trie[p].cnt += v;
  }
}

int minXor(int x)
{
  int res = 0, p = 1;
  for (int i = 31; i >= 0; i--)
  {
    int id = x >> i & 1;
    if (trie[p].nxt[id] and trie[trie[p].nxt[id]].cnt)
      p = trie[p].nxt[id];
    else
    {
      p = trie[p].nxt[id ^ 1];
      res |= 1 << i;
    }
  }
  return res;
}
// Trie Implementation ends

int main()
{
  cin >> n >> q;
  for (int i = 1; i <= n; i += 1)
  {
    cin >> a[i];
  }
  for (int i = 1; i <= q; i += 1)
  {
    cin >> l >> r >> x;
    queries.push_back({{l, r}, {x, i}});
  }
  sort(queries.begin(), queries.end());
  int left = 1, right = 1;
  for (int i = 0; i < q; i += 1)
  {
    int l = queries[i].first.first;
    int r = queries[i].first.second;
    int x = queries[i].second.first;
    int index = queries[i].second.second;
    while (left < l)
    {
      update(a[left], -1);
      left += 1;
    }
    while (right <= r)
    {
      update(a[right], 1);
      right += 1;
    }
    ans[index] = minXor(x);
  }
  for (int i = 1; i <= q; i += 1)
  {
    cout << ans[i] << " \n";
  }
  return 0;
}

Answer 3

编辑：使用 O（位数）代码

使用二叉树存储A的值，看这里：

您需要更改的是向每个节点添加与叶子中的值对应的 A 的索引范围。

# minimal xor in a range
nbits=16    # Number of bits for numbers
asize=5000 # Array size
ntest=50     # Number of random test
from random import randrange

# Insert element a iindex iin the tree (increasing i only)
def tinsert(a,i,T):
for b in range(nbits-1,-1,-1):
    v=((a>>b)&1)
    T[v+2].append(i)
    if T[v]==[]:T[v]=[[],[],[],[]]
    T=T[v]
    
# Buildtree : builds a tree based on array V
def build(V):
T=[[],[],[],[]] # Init tree
for i,a in enumerate(V): tinsert(a,i,T)
return(T)

# Binary search : is T intersec [a,b] non empty ?
def binfind(T,a,b):
 s,e,om=0,len(T)-1,-1
 while True:
  m=(s+e)>>1
  v=T[m]
  if v<a: 
   s=m
   if m==om: return(a<=T[e]<=b)
  elif v>b: 
   e=m
   if m==om: return(a<=T[s]<=b)
  else: return(True) # a<=T(m)<=b
  om=m

# Look for the min xor in a give range index
def minx(x,s,e,T):
 if s<0 or s>=(len(T[2])+len(T[3])) or e<s: return
 r=0
 for b in range(nbits-1,-1,-1):
  v=((x>>b)&1)
  if T[v+2]==[] or not binfind(T[v+2],s,e): # not nr with b set to v ?
   v=1-v
  T=T[v]
   r=(r<<1)|v
 return(r)

# Tests the code on random arrays
max=(1<<nbits)-1
for i in range(ntest):
 A=[randrange(0,max) for i in range(asize)]
 T=build(A)
 x,s=randrange(0,max),randrange(0,asize-1)
 e=randrange(s,asize)
 if min(v^x for v in A[s:e+1])!=x^minx(x,s,e,T):
  print('error')

Answer 4

我能够使用线段树解决这个问题，并尝试按照@David Eisenstat 的建议进行尝试

以下是 C++ 中的实现。我为线段树中的每个线段构建了一个 trie。而求最小异或就是用查询值的每一位()

遍历匹配对应的trie

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < b; i++)
using namespace std;

const int bits = 7;

struct trie {
    trie *children[2];
    bool end;
};

trie *getNode(void)
{
    trie *node        = new trie();
    node->end         = false;
    node->children[0] = NULL;
    node->children[1] = NULL;
    return node;
}

trie *merge(trie *l, trie *r)
{
    trie *node = getNode();
    // Binary 0:
    if (l->children[0] && r->children[0])
        node->children[0] = merge(l->children[0], r->children[0]);

    else if (!r->children[0])
        node->children[0] = l->children[0];

    else if (!l->children[0])
        node->children[0] = r->children[0];

    // Binary 1:
    if (l->children[1] && r->children[1])
        node->children[1] = merge(l->children[1], r->children[1]);

    else if (!r->children[1])
        node->children[1] = l->children[1];

    else if (!l->children[1])
        node->children[1] = r->children[1];

    return node;
}

void insert(trie *root, int num)
{
    int mask = 1 << bits;
    int bin;
    rep(i, 0, bits + 1)
    {
        bin = ((num & mask) >> (bits - i));
        if (!root->children[bin]) root->children[bin] = getNode();
        root = root->children[bin];
        mask = mask >> 1;
    }

    root->end = true;
}

struct _segTree {
    int n, height, size;
    vector<trie *> tree;

    _segTree(int _n)
    {
        n      = _n;
        height = (int)ceil(log2(n));
        size   = (int)(2 * pow(2, height) - 1);
        tree.resize(size);
    }

    trie *construct(vector<int> A, int start, int end, int idx)
    {
        if (start == end) {
            tree[idx] = getNode();
            insert(tree[idx], A[start]);
            return tree[idx];
        }

        int mid   = start + (end - start) / 2;
        tree[idx] = merge(construct(A, start, mid, 2 * idx + 1),
                          construct(A, mid + 1, end, 2 * idx + 2));
        return tree[idx];
    }

    int findMin(int num, trie *root)
    {
        int mask = 1 << bits;
        int bin;

        int rnum = 0;
        int res  = 0;

        rep(i, 0, bits + 1)
        {
            bin = ((num & mask) >> (bits - i));

            if (!root->children[bin]) {
                bin = 1 - bin;
                if (!root->children[bin]) return res ^ num;
            }

            rnum |= (bin << (bits - i));
            root = root->children[bin];
            if (root->end) res = rnum;
            mask = mask >> 1;
        }
        return res ^ num;
    }

    int Query(int X, int start, int end, int qstart, int qend, int idx)
    {
        if (qstart <= start && qend >= end) return findMin(X, tree[idx]);

        if (qstart > end || qend < start) return INT_MAX;

        int mid = start + (end - start) / 2;
        return min(Query(X, start, mid, qstart, qend, 2 * idx + 1),
                   Query(X, mid + 1, end, qstart, qend, 2 * idx + 2));
    }
};

int main()
{
    int n, q;
    vector<int> A;
    vector<int> L;
    vector<int> R;
    vector<int> X;

    cin >> n;
    A.resize(n, 0);

    rep(i, 0, n) cin >> A[i];

    cin >> q;
    L.resize(q);
    R.resize(q);
    X.resize(q);
    rep(i, 0, q) cin >> L[i] >> R[i] >> X[i];

    //---------------------code--------------------//

    _segTree segTree(n);
    segTree.construct(A, 0, n - 1, 0);

    rep(i, 0, q)
    {
        cout << segTree.Query(X[i], 0, n - 1, L[i], R[i], 0) << " ";
    }

    return 0;
}

时间复杂度：O((2n - 1)*k + qklogn)

Space 复杂度：O((2n - 1)*2k)

k -> 位数

如何从给定数组的范围查询中获取给定值和值的最小异或

How to get the minimum XOR of a given value and the value from a query of range for a given array

c++

algorithm

xor

trie

segment-tree