Segment tree : Lazy propagation

0
votes

In an integer array (size 10^5) the operations are like these...

  1. Do bitwise xor operation with every element from index L to R by a particular number X
  2. Find the sum of the numbers from index L to R.

How can i do it with segment tree and lazy propagation ?

2
algorithmdata-structuressegment-tree
I'll add a clue: XOR is associative. (A XOR X) XOR Y) has the same result as A XOR (X XOR Y). - Patricia Shanahan
@Patricia Shanahan , thanks but i knew that. my problem is to find out the segment sum. - palatok
Your problem is to find the segment sum of data that is also subject to XORs on segments. How would you solve the problem if you only had operation 2? - Patricia Shanahan

2 Answers

2
votes

I'd keep, on each node, 32 integers telling me how many ones are there in each position of the binary representation of the child nodes.

To XOR a segment node, it's just a matter of inverting how many ones are there in each position (for each bit 1 in X). 

for i in range(32):
    if X&(1<<i):
        N[i] = (R-L+1)-N[i].

To calculate the sum, 

s = 0
for i in range(32):
    s |= ((N[i]+carry)%2) << i
    carry = (N[i]+carry)/2
1
votes

Your answer is not correct. You need to do some sort of lazy update like here: http://p--np.blogspot.ro/2011/07/segment-tree.html . Else, if you do update(1,n, x) and query(4,5) you will get a wrong answer because the update has changed just the root node.