Saber.HMN's blog

Segment Tree lazy propagation
By Saber.HMN, history, 5 years ago, In English

Given an array of size N.There can be multiple queries of the following types. 1 . Update(l, r, x) : Increment the a[i] (l <= i <= r) with value x. 2 . query(l, r): Find index of the maximum value in the array in a range l to r (both are included).

  • Vote: I like it
  • -4
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +21 Vote: I do not like it

I can't understand your description. Can you post link to source?

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

This can be solved with SQRT decomposition , you just need to save the maximum value and the index with the maximum value for each block and it can be easily updated.

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

    maximum value and the index with the maximum value for each block

    With the index, we can always get back the value. Why save both?

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

      If you use the index to get the current value of some position, you would need to update each array element, which is what you would like to avoid with lazy propagation and similar techniques.

      → Reply