antivenom's blog

How to find Xor of an array segment using segment tree
By antivenom, 9 years ago, In English

Hi everyone.How can I do this question using segment tree with lazy propagation.

Given an array.

query type 1: Find xor from L to R.

query type 2: Update element present at L to X.

query type 3: Update element from L to R to X.

Would anybody mind explaining how to do this question using SEGMENT TREE+LAZY PROPAGATION .I am not really getting Idea behind lazy propagation so please explain to me using this question.Good day.

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Only query of type 3 will need lazy propagation for large number of queries(q1 q2 can be performed in O(logn)).

len = R — L + 1, for [L, R]

after setting [L, R] to all x, final value of xor[l, r] = (len % 2) * x, since only (len % 2) terms remain(x^x=0, 0^x=x).

So, using this idea you can update a node, and mark their children to update.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If it does not trouble you much...would you mind showing me small snippet so I can have better understanding.I have almost got the idea just want to confirm my understanding.And also how one can decide what should we store in lazy array so that it would update the range..Like you did in this question.How to tackle this.BTW Thanks a lot for all your help

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 3   Vote: I like it +1 Vote: I do not like it

      You need to store 'x' in the lazy array. Also you need another array to mark if there is a pending update for each node.

      To better understand, you can try in paper by building a tree(label each node with current value at the node and the segment that intersects the node). For a query 3 [L, R], think how could you perform lazily without updating all segments of size 1 from [L, R]. For each node in the tree at the smallest distance from the root that lies in the segment, you can directly set the final value of the node, and mark the node's children with red color along with value x which means they are to be updated later(we only update them only when necessary).

      → Reply