종류는 아니고.. 누적합, 역누적합

누적합, 역누적합

• 간단하다 a ~ b까지 합을 구하면된다..

• 역누적합은 누적합하기전의 상태를 말한다.

  • 배열에 a부터 b까지(어떤 배열의 누적합) k만큼 늘어난다.

  • A[a] += k, A[b + 1] -= k

예

=> 0 3 3 3 0 0 0 

=> 0 0 0 0 0 0 0


=>역 누적합..

=> 0 3 0 0 -3 0 0

=> update된 누적합 
=> 0 3 3 3 0 0 0

관련 문제

태상이의 훈련소 생활

https://www.acmicpc.net/problem/19951 (태상이의 훈련소 생활)

소스

#include <bits/stdc++.h>

using namespace std;

int n, m;

int a[100000];
int b[100000];
int main()
{

    cin >> n >> m;

    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 0; i < m; i++)
    {
        int s, e, k;
        cin >> s >> e >> k;
        //
        b[s] += k;
        b[e + 1] -= k;
    }

    for (int i = 1; i <= n; i++)
    {
        b[i] += b[i - 1];  // 누적합 과정 
        a[i] += b[i]; //update과정 
        cout << a[i] << " ";
    }

    return 0;
}

/*
=>역 누적합..

=> 0 3 0 0 -3 0 0

=> update된 누적합
=> 0 3 3 3 0 0 0
*/