[Algorithm][Template] Prefix Sum, 구간 합 계산

Prefix Sum : 여러 개의 누적합, 구간합을 묻는 쿼리에 대해 효율적인 알고리즘

• 누적합 : [0, Right] 구간의 합
• 구간합 : [Left, Right] 구간의 합

하나의 구간합을 구하는 것이 O(N)이고 구간합을 구하라는 M개의 쿼리가 들어온다면 시간복잡도는 O(NM)이다.

N = 1,000,000 이고 M = 1,000,000이라면 시간복잡도가 너무 안좋다.

이런 경우 사용하는 것이 Prefix Sum 이다.

누적합을 구해놓고 누적합 간에 -연산을 하면 구간합이기 때문이다.

 

- 시간복잡도 : O(N+M)

- 동작과정

  1) N개의 수에 대하여 접두사 합(Prefix Sum)을 계산하여 배열 P에 저장한다.

  2) 매 M개의 쿼리 정보 [L, R]을 확인할 때 구간 합은 P[R]-P[L-1]이다.

  ▪️ 이때, P[0] 에 0을 넣고 L >= 1 을 만들면 코드가 간결해진다.

 

#include <iostream>
#include <vector>

using namespace std;

int n = 5;
vector<int> data = {10, 20, 30, 40, 50};
vector<int> prefix_sum;

int main(void) {
    // 첫 배열 0 대입
    prefix_sum.push_back(0);

    int sum_value = 0;
    for (auto d : data) {
        sum_value += d;
        prefix_sum.push_back(sum_value);
    }

    int left = 3;
    int right = 4;
    cout << prefix_sum[right] - prefix_sum[left-1] << endl;


    return 0 ;
}

 

다만 위 코드는 90도 회전할 때마다 vector를 선언해 heap영역에 계속 쌓이게 된다.

여러번 돌리면 메모리 관점에서 좋지 않다.

그렇기 때문에 4번이 넘어가는 회전은 4로 나눈 나머지만 회전하는 등 사용에 주의가 필요하다.