코딩테스트-누적합

누적합 (Prefix Sum)

누적합은 배열의 앞에서부터의 합을 미리 계산해 두는 기법이다. 한 번 만들어 두면 임의의 구간 합을 O(1)에 구할 수 있어, 구간 쿼리 문제의 기본기가 된다.

---

핵심 점화식

p[i] = p[i-1] + a[i]

즉 "이전까지의 누적합 + 현재 값"을 계속 더해 나가면 된다.

---

구현

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

int main() {
    int a[6] = {0, 1, 2, 3, 4, 5}; // a[0]은 편의상 0 (1-indexed)
    int p[6] = {0};

    for(int i = 1; i <= 5; i++){
        p[i] = p[i-1] + a[i];   // 누적합 생성
    }

    // 구간 [L, R]의 합 = p[R] - p[L-1]
    int L = 2, R = 4;
    cout << p[R] - p[L-1] << "\n";  // a[2]+a[3]+a[4] = 9

    return 0;
}

구간 합 공식: 구간 [L, R]의 합은 p[R] - p[L-1]로 한 번의 뺄셈이면 끝난다. 이것이 누적합의 핵심 이점이다.

---

구간 쿼리, 두 가지 방법

구간 합을 구하는 대표적인 방법은 두 가지다.

• 누적합 (Prefix Sum) : 배열이 변하지 않을 때 최적. 전처리 O(n), 쿼리 O(1). 단, 값이 중간에 바뀌면 전체를 다시 계산해야 한다.
• 펜윅 트리 (Fenwick Tree / BIT) : 배열 값이 중간중간 바뀔 때 유리. 갱신·쿼리 모두 O(log n)으로 처리한다.

기준	누적합	펜윅 트리
구간 합 쿼리	O(1)	O(log n)
값 갱신	O(n) (재계산)	O(log n)
추천 상황	값이 고정된 경우	값이 자주 바뀌는 경우

---

정리

• 누적합 점화식: p[i] = p[i-1] + a[i]
• 구간 합: p[R] - p[L-1] → O(1)
• 값이 고정이면 누적합, 자주 바뀌면 펜윅 트리.