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, 9 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

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

yes, method of events...

→ Reply
  • »
    »
    9 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
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      And what if we need to query elements?

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

        then there's obviously no solution faster than logn

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

          Why obviously? who proved that?

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

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

            → Reply
    • »
      »
      »
      9 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
      • »
        »
        »
        »
        9 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
    • »
      »
      »
      9 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