Hello,
After having a look at the following blog entry: http://codeforces.net/blog/entry/15729
Quoted Excerpt:
"2.Problems which you are asked to perform some queries asking you to modify a part of elements (without printing queries.) Solution of all of this problems are the same. You just need to know how to solve one of them. Example : You need to perform some queries on an array a1, a2, ...a, n. Each query give you numbers l, r and v and for each i such that l ≤ i ≤ r you should increase ai by v, and then after performing all queries, you should print the whole array. Solution : You should have another array p1, p2, ..., pn which, all of its members are initially 0, for each query, you should increase pl by v and decrease pr + 1 by v . An then, for each i, starting from 1 you should increase pi by pi - 1. So, final array would be a1 + p1, a2 + p2, ..., an + pn . Hard problem of partial sum : Troynacci Query"
Then, having a look at the editorial for Troynacci Query : 100571B - Troynacci Query , Editorial Link: http://codeforces.net/blog/entry/15722
My Question: I find it difficult to trace back the reasoning or mathematical proof behind this algorithm. Could you please suggest any hints how or why this way of solving the problem is correct?
Consider, instead of the array a1, a2, ..., an the array of differences d1, d2, ..., dn where di := ai — ai-1 assuming that a-1 = 0.
What does processing a query (adding x to segment [l,r]) look like in this representation? Once you finish processing all the queries, how do you reconstruct the original array?
thanks for the perspective. I tried that on a paper and really got the idea.