Блог пользователя Saber.HMN

Segment Tree lazy propagation
Автор Saber.HMN, история, 5 лет назад, По-английски

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).

  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

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

→ Ответить
»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить