누적합

누적합이란

 

누적된 합을 담고있는 배열을 이용해 요소들의 합을 빠르게 구하는 방법

 

 

 

왜 씀?

 

11659번: 구간 합 구하기 4 (acmicpc.net)

 

이 문제를 예시로 보자.

 

N개의 숫자가 주어지고,

이 N개의 숫자 배열의 특정구간 i부터 j번째 수까지 합을 M번 구해야한다.

 

N과 M 모두 1부터 100000 사이 수이므로, ]

단순히 for문을 써서 배열의 숫자를 하나씩 sum변수에 더해가는 구현은 O(N^2)의 시간복잡도가 발생한다.

 

그런데 이를 누적합 배열을 이용한다면 O(N)으로 구현이 가능하다.

 

누적합 배열의 각 요소는 i번째 수까지의 합을 의미하기 때문에,

누적합 배열의 요소를 미리 설정해놓고

i번째수 까지의 합을 찾을땐 그냥 누적합 배열에 바로 접근하면 된다.

 

 

#include<iostream>
#include<algorithm>
#define MAX 100000

using namespace std;

int N,M;

int psum[MAX+1];

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> N >> M;
    
    for(int i = 1; i < N+1; i++){
        cin >> psum[i];
        psum[i] += psum[i-1];
    }

    int p,q;
    for(int i = 0; i < M; i++){
        cin >> p >> q;
        cout << psum[q]-psum[p-1] << '\n';
    }

    return 0;
}