webmasteradi's blog

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

By webmasteradi, 10 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

yes, method of events...

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

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

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

      And what if we need to query elements?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        then there's obviously no solution faster than logn

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

          Why obviously? who proved that?

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

            you're free to think a solution exists... =.=

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

      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.

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

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

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

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

      → Reply