CODEWITHSUNDEEP
optimizationdata-structures
nikhil6041
nikhil6041

Reputation: 65

how can we find the xor of elements of an array over the range l,r with a given number x provided there are multiple queries of such type?

For the above questioned i went through some of the query optimization techniques like square root decomposition , binary indexed tree but they don't help in solving my problem optimally . If anybody can suggest an query optimization technique through which i can solve this problem please do suggest.

Upvotes: 0

Views: 181

Answers (1)

m.raynal
m.raynal

Reputation: 3143

You can do that in constant time, using a O(n) space, where n is the size of your array. The initial construction takes O(n).
Given an array A, you first need to build the array XOR-A, in this way:

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

Then you can answer a query on the range (l, r) as follows:

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

We use the fact that for any x, x xor x = 0. That's what makes the job here.

Edit: Sorry I did not understand the problem well at first.
Here is a method to update the array in O(m + n) time, and O(n) space, where n is the size of the array and m the number of queries.
Notation: the array is A, of size n, the queries are (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]

Upvotes: 1

Related Questions