[問題] HackerRank - 陣列的相關問題

[qazkevin (Linus)]

題目: 輸入N與M，N表示陣列個數，M表示操作次數。陣列初始值為0。
          操作內容為輸入a, b, k。a代表第a個元素，b代表第b個元素。
          將a至b的元素(包含a, b兩個位置的元素)加上整數k。
          最後找出陣列元素中最大值。


Sample Input:
5 3
1 2 100
2 5 100
3 4 100

表示N=5, M=3，
所以代表陣列元素有五個，操作次數為三，所以有以下三行操作
第一次操作: a=1, b=2, k=100
第二次操作: a=2, b=5, k=100
第三次操作: a=3, b=4, k=100


Sample Output:
200


Explanation:
第一次操作: 100 100 0 0 0.
第二次操作: 100 200 100 100 100.
第三次操作: 100 200 200 200 100.
所以最大值為 200.


Solution:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    long int N,K,p,q,sum,i,j,max=0,x=0;

    cin>>N>>K;
    long int *a=new long int[N+1]();

    for(i=0;i<K;i++)
    {
        cin>>p>>q>>sum;
        a[p]+=sum;
        if((q+1)<=N) a[q+1]-=sum;
    }

    for(i=1;i<=N;i++)
    {
       x=x+a[i];
       if(max<x) max=x;

    }

    cout<<max;
    return 0;
}

小弟資質愚鈍，一直不懂這個解答的邏輯與演算法，
坦白說思考了兩天，還是看不太懂QQ
請問有哪位大大懂程式碼的想法是什麼嗎?
感激不盡!!!

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.166.24.39
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1515157763.A.C4A.html
→ Sylveon: 考慮數列與前綴和的關係
→ Sylveon: 演算法筆記 Sequence2 最後面
→ qazkevin: Sylveon大大，請問有網址嗎?
→ qazkevin: 請問一下所以第一個for迴圈代表的是把三個序列做微分?
推 fishinair: 我只是直覺的想到，從第幾個到第幾個加多少而已..
→ qazkevin: fishinair大大，我一開始也是這樣寫的...哈哈
→ Sylveon: 我在某個比賽出過一樣的題目xd，你可以考慮只有一個操作
→ Sylveon: 時，把原來數列ai加上k，然後做前綴和(第二個for)的話，
→ Sylveon: 效果就是Si以後的所有項都加上k，因此再用-k吧不要加的
→ Sylveon: 部分抵銷
推 jobsdone: 我是想像成unit step function的疊合,感覺比較視覺化
→ jobsdone: 把題目想像成產生方波,然後方波的疊合這樣子
→ qazkevin: 感謝各位大大的回答，小弟好像對這解法有fu了~