---
id: "imported/blog/study/cs/partialsum"
title: "부분합"
description: "부분합 관련 알고리즘 정리"
kind: "record"
published: "2023-05-22T00:00:00.000Z"
tags: ["sum","segment tree","fenwick tree"]
url: "https://www.readiz.com/blog/study/cs/partialsum/"
markdownUrl: "https://www.readiz.com/blog/study/cs/partialsum/index.md"
---

# 부분합

부분합 관련 알고리즘 정리

## 부분합과 쿼리

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

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

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

```cpp
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)` 이다.

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

```cpp
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를 효율적으로 동작할 수 있게 하는 구조이다.

#### 작성 중