prefix sum

 

누적합에 대한 공부를 진행했다.  

 

이를 다른 말로 구간 쿼리, 여기선 구간 sum 쿼리라고 한다고 한다. 

 

이러한 문제를 푸는 방법은 prefix sum, 펜윅트리 방식들이 있다고 한다. 

 

내가 연습한 예제는 static 배열이여서 prefix sum이 적합하다고 하셨고, 동적 배열, 즉 배열의 각 요소가 동적으로 변경되는 경우는 펜윅트리를 사용해야 한다고 한다. 

 

우선 다음과 같은 문제가 발생한다고 생각해보자. 

 

N개의 자연수이고, M개의 질문을 한다고 가정하자. 

 

예를 들면 10개의 자연수를 주고 3개의 질문을 하는데, 이 질문에는 범위가 포함되어 있다.

 

2부터 5까지 제공된 수의 합을 구하라, 1~10까지의 제공된 수의 합을 구하라. 등등의 질문이 연속적으로 나온다.

 

 

단순하게 접근했을 때 n개의 입력을 받고, m개의 질문에서  제공되는 질문의 범위만큼 반복하여,  누적합을 구할 수 있다. 이에 대한 코드는 다음과 같을 것이다.

 

int main() {
    cin >> n >> m;
    
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    
    int sum = 0;
    for(int i =0; i < m; i++){
        cin >> b >> c;
        int sum = 0;
        
        for( int j = b; j <= c; j++) sum += a[j];
        cout << sum << '\n';
    }
    
    
    return 0;
}

 

 

이 경우 상당히 많은 시간이 소요된다. 이는 n개의 입력을 받는 시간과, m개의 반복에서 누적합을 구하는 과정이 있기 때문이다. 

 

나는 처음에 이를 캐싱이라는 개념으로 접근했었는데, 이게 누적합이랑 약간 비슷하다. 

 

#include <bits/stdc++.h>
using namespace std;

int a[100004], psum[100004], n, m, b,c;

int main() {
    
    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;
}

 

 

이 코드는 누적합의 코드이다. 입력된 숫자를 입력받는 동시 모든 누적합을 구한다. 

다만 누적합을 구하는 과정에서 실제 반복을 통해 구간 누적합을 구하지 않고 미리 캐싱된 배열 값을 통해 입력과 동시에 출력하기 때문에 더 빠르게 처리되는 과정이다. 

 

즉 n과 m만큼 반복은 고정이나, 기존에는 범위만큼의 반복이 추가되었었고, 현재는 범위 반복대신 캐싱된 배열 값을 사용하기에 O(1)로 변경되었다.