webmasteradi's blog

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

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

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

      And what if we need to query elements?

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

        then there's obviously no solution faster than logn

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

          Why obviously? who proved that?

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

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

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

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

    • »
      »
      »
      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?