[PS를 위한 자료구조 8강] 펜윅 트리의 개념과 구현 (Orderstatic Tree)

PS를 위한 자료구조 1-8강

# 펜윅 트리의 개념과 구현 # 에 대해 알아보겠습니다.

​

​

지금까지 세그먼트 트리에 대해 배웠고 잘 따라온 여러분들에게 감사할 따름입니다.

이번 시간에 배워볼 자료구조는 "펜윅 트리"입니다.

펜윅 트리는 세그먼트 트리의 일종으로, 비재귀 세그먼트 트리에 분류할 수 있습니다.

역시 비재귀 세그먼트 트리답게 이해하는게 쉽지는 않지만,

구현 난이도는 비재귀 세그먼트 트리보다도 쉽습니다.

​

아래의 세그먼트 트리의 구조를 다시 봅시다.

​

그런데 이 중에 필요없는 구간이 있지 않을까요?

생각해보면 [1 8] 노드와 [1 4] 노드가 있으면 [5 8] 노드는 필요없는게 아닐까요?

[1 8] 노드의 값에서 [1 4] 노드의 값을 빼준다면 [5 8] 노드의 값을 구할 수 있을 것입니다.

그리고 구간의 끝에 해당하는 값만 남겨 놓아보겠습니다.

​

[1 16]구간에 해당 작업을 수행한 아래의 그림을 봅시다.

​아래에서 눈여겨 보아야하는 특징을 정리하면 다음과 같습니다.

​1. 1부터 16까지 각각 한 번의 숫자만 등장한다.

2. 노드 번호가 2로 n번 나눌 수 있는 경우에 2의 n제곱의 갯수만큼 자료의 갯수를 저장합니다.

​

1번 특징에 대해 이야기하자면, 앞선 비재귀 세그먼트 트리 강의의 마지막에,

원래 세그먼트 트리를 구성할 때에도 최소 2배의 노드가 필요하다고 말씀드렸던 것이 기억날겁니다.

​

겹치는 수행 구간을 제거한다면 그 절반이 될 것이고,

따라서 각 숫자가 1번씩 등장하는 것이 어느정도 납득이 될 것입니다.

​

2번 특징이 펜윅 트리의 핵심이라고 볼 수 있습니다.

예를 들면 12번 노드의 경우 2로 최대 2번 나눌 수 있고,

따라서 12에는 2의 제곱, 즉 4개의 구간의 합이 저장됩니다.

그런데 이 숫자를 빠르고, 간단하게 구할 수가 있습니다.

​

이를 비트 연산의 영역으로 봅시다.

​

2를 최대 2번 나눌 수 있다는 뜻은 이진수에서 끝에 2개의 0이 있다는 뜻입니다.

그리고 그 다음에 1이 나오겠죠.

그리고 이것이, 12를 이진법으로 변환했을 때, 최하위 비트가 될 것입니다.

​

만약 이 최하위 비트 아래는 모두 꺼져있고,

그 위로는 모든 비트가 반대로 되어있는 수를 구할 수 있다면 어떨까요?

​

12는 이진법으로 다음과 같습니다.

12(2) = 00001100

최하위 비트 아래는 모두 꺼지고, 그 위로는 비트가 반대로 되어있는 수는 다음과 같을 것입니다.

11110100

이러한 수가 있다면 최하위 비트만 키는 것은 쉽습니다.

and연산(&)을 해주면 되는거죠.

  00001100
& 11110100
------------
  00000100

그래서 이 수(11110100)는 과연 얼마일까요?

놀랍게도 -12입니다.

컴퓨터에서 -는 2의 보수 연산을 사용합니다.

2의 보수 연산을 구하는 방법은 간단한데, 모든 비트를 뒤집고 1을 더해주면 됩니다.

11110100
-> 00001011 (뒤집기)
-> 00001100 (더하기 1)
-> 12

 

반대로해도 똑같은 결과가 나옵니다.

간단하게 원리를 설명하면 다음과 같습니다.

​

1. 뒤집기를 하면

  (1) 최하위 비트 위로는 모두 뒤집어집니다.

  (2) 최하위 비트 역시 뒤집어집니다.

  (3) 최하위 비트 아래로는 모두 1이 됩니다.

2. 여기서 1을 더해주면

  (1) 최하위 비트 아래 +1이 되고, 모두 1이므로 올림수가 생깁니다.

  (2) 결과적으로 최하위 비트까지 올림수가 생기고, 그 아래는 모두 0이 됩니다.

​

따라서 -와 &만 해주면 최하위 비트를 구할 수 있습니다.

이 최하위 비트가 켜진 수 자체가 바로 각 구간이 가지고 있는 자료의 갯수가 됩니다.

​

즉 x번 수는 x번 자료를 포함하여 x&-x개의 합을 가지고 있는 것입니다.

​

이제 펜윅 트리를 만드는 함수를 설계해봅시다.

int 펜윅[16];

def 전처리(배열 : list) -> list:
    for i in 1 to 16:
        펜윅[i] = SUM(배열[i+1-(i&-i) : i])

위와 같이 하면 O(NlogN)에 전처리를 할 수 있습니다.

하지만 한 번 더해진 숫자가 여러번 더해질 필요는 없겠죠?

O(N)에 전처리해봅시다.

​

1강에서 구간 합 구하기 4를 해결했던 방법을 기억하실 겁니다.

배열 S[i]가 1부터 i까지의 합을 모두 담고있다고 하면 다음과 같이 전처리할 수 있습니다.

def 전처리(배열 : list) -> None:
    for i in 1 to 16:
        펜윅[i] = S[i] - S[i-(i&-i)]

다음과 같이 하면 각 연산을 O(1)에 수행할 수 있으므로 O(N)에 전처리할 수 있게 됩니다.

​보통은 업데이트 연산을 먼저 이야기했지만,

난이도가 있으므로 우선 구간 합 연산부터 이야기해보겠습니다.

​

결론부터 이야기하면 펜윅 트리로는 [L R]의 구간 합을 바로 구할 수 없습니다.

하지만 [1 R], [1 L-1]의 구간합을 구할 수 있습니다. 이들의 차이를 구하면 [L R]의 구간합을 구할 수 있습니다.

이게 별거인가? 생각하실 수도 있지만, 이는 펜윅트리의 치명적인 단점이 되기도 합니다.

​

최솟값, 최대값을 구해야하는 상황을 예시로 들 수 있습니다.

이 둘은 덧셈처럼 역연산이 존재하지 않습니다.

[1 R]의 최솟값, [1 L-1]의 최솟값을 아는 것만으로는 [L R]의 최솟값을 구할 수 없죠.

지난 시간에 배웠던 금광 세그 테크닉도 사용할 수 없습니다.

따라서 펜윅트리를 사용할 수 있는 경우는 매우 한정되어있다고 볼 수 있습니다.

하지만 구현이 간단하고, 세그먼트 트리 중,

최고의 성능과 메모리 사용량을 가지고 있다는 장점을 무시할 수는 없습니다.

​

[1 R]까지의 구간 합을 구하는 과정을 설명드리겠습니다.

​

1. R번째 노드에는 R&-R개의 구간합이 저장되어 있을 것입니다.

2. R번 노드를 선택하면 문제는 [1, R-(R&-R)]로 축소됩니다. 1번을 반복합니다.

3. R&-R은 최하위 비트를 의미하므로 항상 1보다 큽니다. 따라서 언젠가 [1 0] 구간에 도달하게 됩니다. 이때 반복문을 탈출합니다.

​

시간 복잡도는 어떻게 될까요?

​

1. R-(R&-R)를 보면 R에서 최하위 비트만 켜져있는 것을 빼주는 것이므로, 최하위 비트를 끄는 연산으로 볼 수 있습니다.

2. 따라서 매번 비트가 1개가 꺼지게 됩니다.

3. 비트는 최대 LogN개까지 가지고 있을 수 있으므로 시간복잡도는 O(logN)가 됩니다.

​

위 알고리즘을 다음과 같이 설계할 수 있습니다.

def 1_to_번호_쿼리(번호 : int) -> int:
    리턴값 = 0
    while 번호 > 0:
        리턴값 += 펜윅[R]
        번호 -= (번호&-번호)
    return 리턴값

따라서 [L R] 구간의 합은 다음과 같이 구할 수 있습니다.

​

def L_to_R_쿼리(L : int, R : int) -> int:
    return 1_to_R_쿼리(R) - 1_to_R_쿼리(L)

구현이 이렇게 간단할 수가 없죠?

이게 끝입니다.

​

그럼 이제 업데이트 연산에 대해 알아봅시다.

​

i번째 원소를 업데이트 한다고 했을 때,

i번 노드를 포함하여, i번 원소를 가지고 있는 모든 범위의 노드가 바뀌어야할 것입니다.

​

다음과 같이 논의를 해보겠습니다.

​

1. i를 포함할 수 있는 노드의 인덱스는 i보다 크거나 같을 것입니다.

2. 최하위 비트를 빼주었을 때, i보다 작은 값이 될 수 있으려면 최하위 비트가 i의 최하위 비트보다 커야합니다.

3. 따라서 i를 포함할 수 있는 가장 작은 노드는 바로 i보다 최하위 비트가 높은 최소의 번호 노드입니다.

4. 이러한 원소는 i에 i의 최하위 비트를 더해준 값입니다. 즉 i+(i&-1)입니다. 

​

즉 최하위 비트를 계속 더해주면서 업데이트하고, 이를 트리의 범위를 벗어날 때까지 반복합니다.

시간 복잡도는 어떨까요?

​

1. 최하위 비트를 계속 더해주는데, 최소 1개의 최하위 비트가 상위 비트로 이동합니다.

2. 이런 연산은 최대 LogN번까지만 반복할 수 있으므로 시간복잡도는 O(logN)이 됩니다.

​

이제 함수를 설계해봅시다.

def 업데이트(int 번호, int 추가값)-> None:
    while 번호 <= 마지막:
        펜윅[번호] += 1
        번호 += 번호&-번호

끝입니다. 이렇게 간단할 수가 없습니다.

​위 설명을 토대로 구현한 펜윅 트리 코드를 첨부합니다.

​

1. 파이썬

arr = [*range(1, 257)]  # 1부터 256
prefix = [0]*257

for i in range(1, 257):
    prefix[i] = prefix[i-1] + arr[i-1]

Fenwick = [0]*257

for i in range(1, 257):
    Fenwick[i] = prefix[i] - prefix[i-(i & -i)]


def update(idx, plus):
    while idx <= 256:
        Fenwick[idx] += plus
        idx += idx & -idx


def query_1_to_idx(idx):
    ret = 0
    while idx:
        ret += Fenwick[idx]
        idx -= idx & -idx
    return ret


def query_L_to_R(L, R):
    return query_1_to_idx(R) - query_1_to_idx(L-1)


print(query_L_to_R(2, 5))   # 2+3+4+5 = 14
update(3, 3)                # 3->6
print(query_L_to_R(2, 5))   # 2+6+4+5 = 17

 

​

2. c++

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

vector<ll> Fenwick;
int n;

void build(vector<ll> &arr){
    n = arr.size();
    Fenwick.resize(n+1);
    vector<ll> pre(n+1);
    for (int i=0; i<n; ++i) pre[i+1] = pre[i] + arr[i];
    for (int i=1; i<=n; ++i) Fenwick[i] = pre[i] - pre[i&-i];
}

void update(int idx, int plus){
    for (; idx <= n; idx += idx&-idx) Fenwick[idx] += plus;
}

int query_1_to_idx(int idx){
    ll ret = 0;
    for (; idx; idx -= idx&-idx) ret += Fenwick[idx];
    return ret;
}

int query_L_to_R(int L, int R){
    return query_1_to_idx(R) - query_1_to_idx(L-1);
}

연습문제는 따로 없습니다.

여러분들이 지금까지 해결해온 문제 중 펜윅트리로 해결할 수 있는게 있을겁니다.

​

​

피드백 및 오류 지적은 언제나 환영입니다.

​

질문은 댓글로 해주셔도 되고, 제 유튜브 채널을 방문해서 하셔도 되고, 오픈채팅방으로 하셔도 됩니다.

​

[유튜브 : 승욱은] 승욱은 - YouTube

[ 1:1 오픈채팅방] 카카오톡 오픈채팅 (kakao.com)

​

[Refernce] 펜윅 트리 (바이너리 인덱스 트리) (acmicpc.net)