PrefixSum
in Computer Science on Algorithm
PrefixSum
누적합이란 요소들의 누적된 합의 의미로 어떠한 배열을 기반으로 앞에서 부터 요소들의 누적된 합을 저장해 새로이 배열을 만들어서 이를 활용하는 것을 말한다. 만약 문제에서 구간합 쿼리 즉 구간쿼리가 왔을 때 누적된 합을 통해서 -연산을 통해서 문제를 해결한다. 예를 들어서 psum[5] - psum[1] 이라면 구간합 2부터 5까지의 합이 된다.
코드
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[100004],b,c,psum[100004],n,m;
int main(){
ios_base::sync_with_stdio(false),cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> a[i];
psum[i] = psum[i - 1] + a[i];
}
for(int i = 0; i < m; i++){
cin >> b >> c;
cout << psum[c] - psum[b - 1] << '\n';
}
return 0;
}
여기서 주의할 점은 psum[i] = psum[i - 1] 이라는 점인데 순회를 할 때 1부터 순회를 해야한다는 점이다. 그 이유는 psum에 만약에 0이 들어간다면 배열을 아예 참조할 수 없는 문제가 발생한다.