data structure for special type of queries

Question

I have faced some problems of this kind. Suppose we are given an array A of n elements where n is around 1 million. We are given queries of form 'p q'. In each query, we have to perform some operation on the elements A[p] to A[q].

• This operation is some ordinary operation like XOR or something. For ex- taking XOR of every number in A( from index p to q )with a given number m. For ex- A[p]^m,A[p+1]^m..A[q]^m

If we are given thousands of queries of type 'p q' then, we do repetitive calculations for overlapping ranges (for ex.-p1<p2<q1<q2). If have a space/time tradeoff, I would prefer to do my work faster even if it takes more space. So, I am concentrating on time not much on space.

My question is - Is there any data structure which can process these type of queries(having some range which repeats in further queries) efficiently. What I can think of is something like- doing some pre-processing and saving things in a data structure. And then updating and processing as we receive further queries.

Can someone suggest some data structure which is helpful in processing the queries which are concerned with some ranges (specially when the ranges are further repeated extensively)?

• This is the original question for which I need the data structure-
  maximum value of xor operation

Answer 1

The first thing I thought of was a Segment Tree with lazy propagation but it only really applies if the query you described is really an update to the table and doesn't return the result. So, there would be an update[p q] operation and a query[p q]. The first just updates using an operation like you described and the second returns the values from the range.

Also see this.

Answer 2

For each k in the range 0 to log(n) store an array A[k] of length n/2**k.

The contents of A[k][i] will represent the elements in the array from index i*2**k to (i+1)2*k-1.

When you want to operate on a range you break the range into the biggest chunks possible and update the corresponding entries in A[k].

e.g. if you had a range from 16->33 you would update just A[4][1] (representing 16->31) and A[1][16] (representing 32->33)

When you want to access the combined value in an element you need to combine the operations in each of the log(n) arrays.

e.g. to access 5 you would need to combine operations in A[0][5] and A[1][2] and A[2][1] and A[3][0] etc.

This should give O(log(n)) cost for each operation on a range, and for each access of an element.