누적합

누적합이란 요소들의 누적된 합의 의미로 어떠한 배열을 기반으로 앞에서 부터 요소들의 누적된 합을 저장해 새로이 배열을 만들어서 이를 활용하는 것을 말한다.

psum[]이란 배열을 만들어서, 0번 인덱스는 비워두고

이런 식으로 구현이 가능하다. 시간복잡도를 확 줄일 수가 있다.

예시 문제

백준 11441 : 합구하기
문제바로가기

#include <iostream>
#include <vector>
#include <algorithm>
#define fastio cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(false);
using namespace std;

int n, m, tmp1, tmp2;
int tmp;
int psum[100004];
int a[100004];

int main(){
    fastio;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> tmp;
        psum[i] = psum[i - 1] + tmp;
    }
    cin >> m;
    for(int i = 0 ; i < m ; i++){
        cin >> tmp1 >> tmp2;
        cout << psum[tmp2] - psum[tmp1 - 1] << '\n';
    }
}