Mathematical Proof for Partial Sum Problems

Revision en1, by thecortex, 2016-11-23 13:49:22

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?

Tags partial sum, series, #trees, #dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English thecortex 2016-11-23 13:49:22 1318 Initial revision (published)