If we have to perform range update query many times, Can we reduce the overall time?
If we have to perform range update query many times, Can we reduce the overall time?
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3382 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
yes, method of events...
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...
And what if we need to query elements?
then there's obviously no solution faster than logn
Why obviously? who proved that?
you're free to think a solution exists... =.=
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.
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].
If in case we have large number of point update queries,can we also reduce the overall time?