时间戳

首页 > 解决方案 > 如果存在多个这种类型的查询，我们如何找到给定数字 x 在 l,r 范围内的数组元素的异或？

optimization - 如果存在多个这种类型的查询，我们如何找到给定数字 x 在 l,r 范围内的数组元素的异或？

问题描述

对于上述问题，我经历了一些查询优化技术，如平方根分解、二叉索引树，但它们无助于以最佳方式解决我的问题。如果有人可以建议我可以解决此问题的查询优化技术，请提出建议。

标签： optimizationdata-structures

解决方案

您可以在恒定时间内使用O(n)空格来执行此操作，其中n是数组的大小。初步建设需要O(n)。
给定一个数组A，你首先需要构建数组XOR-A，这样：

XOR-A[0] = A[0]
For i from 1 to n-1:
  XOR-A[i] = XOR-A[i-1] xor A[i]

然后您可以回答范围 (l, r) 的查询，如下所示：

get_xor_range(l, r, XOR-A):
  return XOR-A[l-1] xor XOR-A[r]

我们使用事实，对于任何x, x xor x = 0。这就是这里的工作。

编辑：对不起，我一开始没有很好地理解这个问题。
这里是一种及时更新数组的方法O(m + n)，O(n)空间，这里n是数组的大小和m查询的次数。
符号：数组为A，大小n为 ，查询为(l_i, r_i, x_i), 0 <= i < m 

L <- array of tuple (l_i, x_i) sorted in ascending order by the l_i 
R <- array of tuple (r_i, x_i) sorted in ascending order by the r_i
X <- array initialised at 0 everywhere, of size `n`
idx <- 0
l, x <- L[idx]
for j from 0 to n-1 do:
  while l == j do:
    X[j] <- X[j] xor x
    idx ++
    l, x <- L[idx]
  if j < n then X[j+1] <- X[j]

idx <- 0
r, x <- R[idx]
for j from 0 to n-1 do:
  while r == j do:
    X[j] <- X[j] xor x
    idx ++
    r, x <- R[idx]
  if j < n then X[j+1] <- X[j]

for j from 0 to n-1 do:
  A[j] <- A[j] xor X[j]

推荐阅读