[알고리즘/C++] 누적합과 구간합 쿼리

prefix sum.

기본적으로 배열의 0번째 인덱스는 비워둔다.

누적합 배열 psum의 1번째 인덱스는 1번째까지 더한것.

2번째 인덱스는 2번째 까지 더한 것.

3번째 인덱스는 3번째 까지 더한 것을 저장하는 식으로 간다.

( 예를들어 홀수를 누적합한 배열을 구할 시 psum[1] = 1, psum[2]= 1+3, psum[3] = 1+3+5 ...)

 

뒤에서 부터 더하는 suffix sum도 있지만, 코딩테스트에서는 prefix sum밖에 안나온다.

 

구간합 쿼리: 구간에대한 합을 구하라

 

 

구간쿼리라고 하면 두가지가 생각나야한다.

1. 누적합 psum

2. 펜윅트리

 

정적 배열인 psum.

요소들이 순간순간 중간에 변하는 동적배열이라면 누적합을 쓸 수가 없다.

펜윅트리를 써야한다.

 

 

 

구현 순서는 다음과 같ㄷ.

1. 누적합을 psum 배열에 구현한다. ​

2. psum의 차를 활용해 구간합 쿼리를 구한다.

 

psum을 만드는 코드는 다음과 같다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[10004], b, c, psum[10004], n, m;
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    //n: psum의 길이, m: 구간합 쿼리가 반복되는 횟수
    cin >> n >> m;

    //psum 생성
    for(int i=1; i=n; i++){
        cin >> a[i];
        psum[i] = psum[i-1] + a[i];
    }

    //psum 구간합쿼리 구하기 
    for(int i = 0; i<m; i++){
        //b~c사이 구간합 구하기
        cin>>b>>c;
        cout<<psum[c] - psum[b-1]<<"\n";
    }

    // 입력 예시
    /* 
        8 3
        1 2 3 4 5 6 7 8
        1 4
        1 5
        3 5
    */

}