159. Fenwick Tree

세그먼트 트리의 변형 버전인 펜윅 트리(Fenwick Tree)에 대해 알아본다.

---

펜윅 트리는 세그먼트 트리의 구조를 응용하여 원소들의 값이 변할 수 있을 때 누적합을 빠르게 구할 수 있게 하는 자료 구조이다. 먼저 합 세그먼트 트리에서 누적합을 구할 때 어떤 노드들이 사용되는지 확인해 보자.

합 세그먼트 트리를 설명할 때 노드들에 위와 같이 번호를 매기는 것이 일반적이라고 했다. 여기서 앞쪽 $k$개 원소의 누적합을 구할 때 합에 포함되는 노드들의 번호를 나열하면 다음과 같다.

$k=1$인 경우: $8$

$k=2$인 경우: $4$

$k=3$인 경우: $4$, $10$

$k=4$인 경우: $2$

$k=5$인 경우: $2$, $12$

$k=6$인 경우: $2$, $6$

$k=7$인 경우: $2$, $6$, $14$

$k=8$인 경우: $1$

일부 노드들만 합에 포함된다는 것을 알 수 있다. 표시를 해 보면 다음과 같다.

각 노드의 오른쪽 자식 노드들이 포함되지 않았는데, 이유를 분석해 보면 오른쪽 자식 노드가 합에 포함될 경우 왼쪽 자식 노드도 합에 포함되어야 하고, 그러면 두 노드를 부모 노드 하나로 대체할 수 있어 오른쪽 자식 노드를 합에 포함할 필요가 없어지기 때문임을 알 수 있다. 그렇다면 합 세그먼트 트리로 누적합을 구할 때 검은색 노드들은 사실상 필요가 없다. 이제 이 노드들을 전부 지우고 남은 노드들의 연결 상태를 변형하면 다음과 같은 트리를 얻을 수 있다.

이 트리에서 각각의 노드에 대응하는 구간의 끝 원소의 인덱스는 모두 다르다. 이 값을 노드 번호로 하면 다음과 같다.

이 트리에서 부모 노드에 대응하는 구간은 각 자식 노드에 대응하는 구간을 모두 포함한다.이때 각 자식 노드에 대응하는 구간은 서로 겹치지 않는다.또한 $k$번 원소는 $k$번 노드와 그 조상 노드들에 대응하는 구간에 포함된다. 따라서 $k$번 원소의 값을 갱신할 경우 $k$번 노드와 그 조상 노드들의 값을 갱신하면 된다. 노드가 $n$개인 펜윅 트리의 높이는 $\lg n$이므로 펜윅 트리에서 값을 갱신하는 시간은 $O(\lg n)$이다.

 

앞쪽 $k$개 원소의 누적합을 계산할 경우, $k$번 노드의 값에 $k$번 노드에 대응하는 구간을 제외한 나머지 누적합을 구하면 된다. $k$번 노드에 대응하는 구간의 길이는 $k$에서 값이 $1$인 최하위 비트와 같고, 이 값은 $k \And -k$로 나타낼 수 있음이 알려져 있다.즉 $k$번 노드에 대응하는 구간은 $[k - (k \And -k) + 1, k]$로 나타낼 수 있고, $k$개 원소의 누적합은 $k$번 노드의 값에 $k - (k \And -k)$개 원소의 누적합을 더하면 된다. $k$에서 값이 $1$인 비트의 개수는 최대 $\lg k + 1$개이므로 노드가 $n$개인 펜윅 트리에서 누적합을 계산하는 시간은 $O(\lg n)$이다.

 

구현은 다음과 같다. 때때로 구현 미스가 나서 $\text{REP}(0)$을 호출하는 경우가 있는데 이러면 함수 내부에서 무한 루프에 걸리므로 주의해야 한다.

int n, a[100005];

void REP(int i, int v)
{
    int k = v - a[i];
    for(; i <= n; i += i & -i)a[i] += k;
}
int getSum(int i)
{
    int s = 0;
    for(; i ; i -= i & -i)s += a[i];
    return s;
}

원소가 입력되고 처음부터 노드들의 값을 계산해야 할 경우 다음과 같이 전처리하면 된다.

for(int i = 1; i <= n; i++)cin >> a[i];
for(int i = n; i; i--)a[i] -= a[i - i & -i];

 

[연습문제]

 

BOJ 2268. 수들의 합 7 (Gold I)

구간 합은 누적합의 차로 계산할 수 있으므로 펜윅 트리를 사용하여 구간 합을 구할 수 있다.

 

BOJ 18436. 수열과 쿼리 37 (Gold I)

홀수를 $1$, 짝수를 $0$으로 치환하면 펜윅 트리로 문제를 해결할 수 있다.

 

BOJ 16975. 수열과 쿼리 21 (Platinum IV)

구간 업데이트 + 점 쿼리를 처리해야 하는데, $a_0 = 0, b_i = a_i - a_{i-1}$으로 정의하고 쿼리를 $b_i$에 적용하면 $1$번 쿼리는 $b_i$에 $k$를 더하고 $b_{j+1}$에서 $k$를 빼는 것과 같고 $2$번 쿼리는 $b_1$부터 $b_x$까지의 합을 구하는 것과 같다. 즉 점 업데이트 + 구간 쿼리가 되므로 펜윅 트리를 사용해서 문제를 해결할 수 있다.