rajkumar62506's blog

Range Update for XOR queries in segment tree
By rajkumar62506, history, 4 years ago, In English

Hello, Is it possible to do range add query in segment tree for XOR queries as we can do for sum queries. I am not finding way to do it. Because for range add for sum, we can update parent node and push update for child so we can use lazy propagation. But for range add for XOR queries how can we update parent node without updating child nodes?

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

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

You probably want to specify what range update you're referring to (is it range add or range set or other). Anyways, for lazy seg tree, all range updates need to satisfy the property that if given a segment value and segment length, you can apply the operation to that segment (in constant time) without further information. Taking the example of sum queries, range add satisfies this property because you can return value+length*add_value, and range set satisfies this property because you can return length*set_value. For xor queries, range set satisfies this property as you can return (length%2)*set_value. However, range add doesn't satisfy this property (this follows intuitively, and you can verify this for yourself by considering xor value = 1 and add_value = 1. In this case both 0^1 = 1 and 2^3 = 1 but (0+1)^(1+1) = 3 != (2+1)^(3+1) = 7)

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

    Sorry, I forgot to specify query. Actually I was asking for Range add query. Now my doubt is clear from your explanation.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    Hey, thank you so much for this comment! I have been confused for very long on lazy segtree and this cleared a lot. I think this must be one of the most important comments on Codeforces.

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

Auto comment: topic has been updated by rajkumar62506 (previous revision, new revision, compare).

→ Reply