Search code examples
algorithmdata-structuressegment-tree

Segment tree : Lazy propagation

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 ?

Solution

  • 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