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]

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