부분합 관련 알고리즘 정리

부분합과 쿼리

Query란, 이를테면 특정 Range의 합을 구하는 것을 말한다. 이러한 Query에 따라 부분합을 저장하는 방식을 다르게 해야한다.

배열이 변하지 않고 Query가 계속될 경우

이 경우에는 가장 단순하면서도 심플한 방법이 있다.

int pSum[MAX];
void init(int arr[]) {
    pSum[0] = arr[0];
    for(int i = 1; i < MAX; ++i) {
        pSum[i] = pSum[i-1] + arr[i];
    }
}
int getRangeSum(int l, int r) {
    if (l == 0) return pSum[r];
    return pSum[r] - pSum[l - 1];
}

이 경우 처음 init이 된 이후에는 무려 O(1)로 부분합을 구할 수 있다.

그런데, 이렇게만 되면 너무 쉬우니, 보통 알고리즘 시험이나 이런 곳에서는 arr의 값을 지속적으로 변경하는 형태의 문제가 출제되곤 한다. 이렇게 원본 배열의 값이 변화가 있을 경우에는 기존에 구해놓은 pSum의 값이 무용지물이고, 값에 변화가 있을 때마다 O(n)의 업데이트가 있어야 할 것이다.

Fenwick Tree

부분합을 구할 때 있어서 가장 아름다운 방법이라고 나는 생각한다. 이 트리는 Binary-Indexed Tree 라고도 불리며, 추후 소개할 Segment Tree와 다르게, 추가 메모리 공간을 N 만큼만 사용하고도 부분합을 저장할 수 있는 방법이다. 어떻게 N 만큼으로 저장하는가? 이진수의 원리를 사용한다. 예를들어 특정 Index의 값을 업데이트 한다고 하면, 아래처럼 한다.

• 11 (1011) -> 12 (1100) -> 16 (10000) -> 32 (100000) -> ...
• 7 (0111) -> 8 (1000) -> 16 (10000) -> 32 (100000) -> ...

이렇게 할 경우, 전체 업데이트 될 Index의 개수는 log n개가 되므로, 시간복잡도가 O(n)에서 많이 줄어들게 된다.

그리고, 특정 Index 까지의 합을 구하고 싶다면, 아래 순서로 합한다.

• 11 (1011) -> 10 (1010) -> 8 (1000)
• 7 (0111) -> 6 (0110) -> 4 (0100)

이 과정도 마찬가지로 이진수 단위로 업데이트 되므로 시간복잡도는 O(log n) 이다.

코드로 위 두 과정을 구현하면 아래처럼 된다.

int f[MAX];
void update(int idx, int v) {
    for(; idx < MAX; idx += idx & -idx) f[idx] += v;
}
int get(int idx) {
    int r = 0;
    for(; idx > 0; idx -= idx & -idx) r += f[idx];
    return r;
}

코드에서 드러난 것처럼, 만약 n개의 데이터를 초기화한다고 하면 O(n log n)의 시간복잡도가 소요된다.

Segment Tree

Segment Tree는 일반적인 Query를 효율적으로 동작할 수 있게 하는 구조이다.

작성 중