You are viewing a single comment's thread. Return to all comments →
Hello, I don't really get your DIFF representation, but here is the deal:
you need to keep in mind that at the end of queries to get the real value of i we need to sum the values of A[0]->A[i].
for a query (l, r, x) if we add x to A[l] then we're sure later for every k in [l, r] sums(0->k) will include x.
the problem is that every k > r will also include that x, therefore we'll decrement l[r+1] by x.
Now the sum through 0 -> k will include x only if k >= l and will exclude it only if k > r which is equivalent to:
sum(0->k) will consider x only if k is in [l, r]
Seems like cookies are disabled on this browser, please enable them to open this website
Array Manipulation
You are viewing a single comment's thread. Return to all comments →
Hello, I don't really get your DIFF representation, but here is the deal:
you need to keep in mind that at the end of queries to get the real value of i we need to sum the values of A[0]->A[i].
for a query (l, r, x) if we add x to A[l] then we're sure later for every k in [l, r] sums(0->k) will include x.
the problem is that every k > r will also include that x, therefore we'll decrement l[r+1] by x.
Now the sum through 0 -> k will include x only if k >= l and will exclude it only if k > r which is equivalent to:
sum(0->k) will consider x only if k is in [l, r]