안녕하세요! 소리입니다 👋
이번 글에서는 부분합을 빠르게 구하면서도 단일 원소 갱신을 세그먼트 트리처럼 $O(logN)$ 시간에 갱신이 가능하도록 만드는 자료구조인 펜윅 트리(Fenwick Tree)에 대한 내용을 준비했어요.

---

🚀 펜윅 트리란?

일반적인 부분합 배열은 배열 $A$의 $k$번째 요소가 $\sum_{i=1}^{k} A_i$의 값을 가져요.
이렇게 하면 $k$까지의 부분합을 구할 때, $A_k$에 접근만 하면 되기 때문에 부분합을 빠르게 구할 수 있어요.
그러나 부분합을 이루는 데이터가 바뀌면 부분합 배열을 새로 구성해야 하기 때문에 $O(N)$의 시간이 걸리게 되죠.

펜윅 트리는 부분합 배열에서 빠른 갱신을 지원하기 위해 배열 인덱스의 비트 성질을 이용해 빠른 갱신을 가능하도록 만든 자료구조예요.
모든 요소가 부분합 값을 가지는 것이 아닌, 각 인덱스가 특정 범위를 담당하게 해서 갱신을 $O(logN)$ 시간에 가능하도록 만들어요.

구성 조건

데이터를 펜윅 트리로 구성하기 위해서는 역연산과 결합 법칙을 만족해야 해요.

🤔 역연산이란?

역연산은 연산이 적용된 값을 원래대로 되돌리는 연산을 말해요.
예를 들어 어떤 수 $N$에 2를 더하는 연산이 적용되었다면, 2를 빼는 연산을 통해 원래 값으로 돌릴 수 있어요.

부분합 자체에서는 역연산이 필수 조건이 아니지만, 부분합을 이용해 구간합을 구하기 위해서는 역연산이 존재해야 해요.

🤔 결합 법칙이란?

결합 법칙은 연산이 반복될 때, 연산 순서와 상관없이 계산 후 같은 값을 도출하는 것을 말해요.
세그먼트 트리는 분할 정복의 원리로 구간 요청을 처리하기 때문에, 데이터가 결합 법칙을 만족해야 사용할 수 있어요.

결합 법칙이 성립하는 대표적인 연산으로는 덧셈과 곱셈이 있어요.

• 덧셈의 결합 법칙
  $(X+Y)+Z=X+(Y+Z)$

🧑‍💻 펜윅 트리의 동작과 구현

펜윅 트리 배열 선언

펜윅 트리는 데이터의 크기만큼의 공간으로 구현이 가능해요.
다만, 비트 성질을 편하게 이용하기 위해서는 첫 노드를 $1$번으로 시작하는 것이 유리해요.
따라서 $N+1$의 크기의 배열을 만들었어요.

let mut tree = vec![0; n + 1]

데이터 갱신하기

어떻게 하면 특정 인덱스를 담당하는 노드들을 방문할 수 있을까요?
데이터를 갱신할 특정 인덱스에서 시작하여 현재 위치의 범위만큼을 더해 가면 담당하는 노드를 모두 방문할 수 있어요.

각 인덱스가 담당하는 범위는 인덱스를 나눌 수 있는 가장 큰 $2^k$와 같아요.

💡 어떤 수를 나눌 수 있는 가장 큰 $2^k$ 구하기

어떤 수 $N$을 나누는 $2^k$의 값은 $N$의 하위 비트와 관련이 있어요.

어떤 수가 짝수라는 것은 그 수의 최하위 비트가 $0$이라는 뜻과 같아요.
짝수는 $2$의 배수이고, $2_{(10)}=10_{(2)}$이기 때문이에요.
어떤 수가 $2^k$의 배수라면 $2$로 $k$번 나눌 수 있어야 하기 때문에, $N$의 최하위 비트에는 $0$이 $k$개 와야 해요.

$2^k$ 값은 다음 연산으로 구할 수 있어요.

n & -n

$11$번 인덱스를 갱신하는 것으로 예를 들어볼게요.
$11$번 인덱스를 갱신하기 위해서는 $11$번과 $12$번, $16$번 인덱스의 갱신이 필요해요.

시작은 $11$번 인덱스예요.
$11$번 인덱스는 자신의 인덱스만 담당하므로, 다음으로 방문하게 되는 인덱스는 $12$번이에요.
$12$번 인덱스는 $4$의 범위를 담당하므로, 다음으로 방문하게 되는 인덱스는 $16$번이에요.
$16$번 인덱스는 가장 상위의 노드이므로, $16$번을 끝으로 방문이 완료돼요.

이 부분을 다음 코드로 구현할 수 있어요.
아래 코드는 idx 노드에 val 값을 더하는 코드예요.

fn add(tree: &mut [i32], mut idx: usize, val: i32) {
	// 최상위 노드 방문할 때까지 반복
	while idx < tree.len() {
        tree[idx] += val;
        
        // 다음 인덱스 계산
        idx += idx & -(idx as isize) as usize;  // idx & (!idx + 1); 으로 대체 가능
    }
}

부분합 구하기

부분합을 구하는 방법도 데이터를 갱신하는 방법과 매우 유사해요.
데이터 갱신 동작과 달리 범위를 빼면 계산에 필요한 인덱스를 모두 방문할 수 있어요.

$1$번부터 $11$번까지 부분합을 구해볼게요.

먼저 $11$번에서 출발해요.
$11$번의 범위를 빼면 $10$번이에요.
$11$번 인덱스는 자신의 인덱스만 담당하므로, 다음으로 방문하게 되는 인덱스는 $10$번이에요.
$10$번 인덱스는 2의 범위를 담당하므로, 다음으로 방문하게 되는 인덱스는 $8$번이에요.
$8$번 인덱스는 가장 왼쪽의 노드이므로, $8$번을 끝으로 방문이 완료돼요.

이 부분을 다음 코드로 구현할 수 있어요.

fn query(tree: &[i32], mut idx: usize) -> i32 {
    let mut res = 0;
    while 1 <= idx {
        res += tree[idx];
        idx -= idx & -(idx as isize) as usize;  // idx & (!idx + 1); 으로 대체 가능
    }
    res
}

---

지금까지 부분합을 구하는 자료구조인 펜윅 트리에 대해 알아봤어요.
펜윅 트리는 부분합을 구하고 원소를 갱신할 때 비트 연산을 사용하는 탓에 처음엔 조금 낯설 수 있어요.
그러나 펜윅 트리의 구조를 이해하면 간단한 코드로 갱신이 효율적인 부분합을 구현할 수 있어요.

다음에도 유익한 내용으로 찾아올게요! 😁