thecortex's blog

Mathematical Proof for Partial Sum Problems
By thecortex, history, 8 years ago, In English

Hello,

After having a look at the following blog entry: http://mirror.codeforces.com/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://mirror.codeforces.com/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?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    thanks for the perspective. I tried that on a paper and really got the idea.

    → Reply