Блог пользователя webmasteradi

Can we perform a large number of Range Update and Point Update Queries in less than Amortized log(n) time?

Автор webmasteradi, 10 лет назад, По-английски

If we have to perform range update query many times, Can we reduce the overall time?

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

yes, method of events...

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

    for example:
    you want to apply update "L R x" — add x on segment [L;R]
    then just add event1 (time = L, change = +x), and event2 (time = R + 1, change = -x)
    then just go from 1 to n and apply your events to calculate current element...

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

      And what if we need to query elements?

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

      What is the pre-processing required,and meaning of this line "_go from 1 to n and apply your events to calculate current element.._" Can you explain in detail Please! I am a beginner.

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

        When you have query update L R x, you can do it in O(1): arr[L]+=x;arr[R+1]-=x; Then the value of the element on position i will be arr[1]+arr[2]+...+arr[i].

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

      If in case we have large number of point update queries,can we also reduce the overall time?

      → Ответить