• + 1 comment

    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]