펜윅 트리 (Binary Indexed Tree)

세그먼트 트리와 매우 비슷하지만, 구현이 훨씬 간단한 펜윅 트리(Fenwick Tree) 에 대해 알아보자.

 

펜윅 트리도 구간 수정과 쿼리를 수행할 수 있지만, $1$~$i$ 까지의 구간에 대해서만 연산할 수 있다.

때문에 보통은 누적합에 대한 쿼리와 수정 연산에 사용된다.

 

펜윅 트리의 동작 과정에 대한 간략한 설명만 하고 자세한 설명은 생략한다.

*https://www.acmicpc.net/blog/view/21

*https://www.topcoder.com/community/competitive-programming/tutorials/binary-indexed-trees/

 

위 그림과 같이 BIT 에서의 배열의 각 칸은 자신으로부터 이진수 표현의 마지막 비트 전까지의 구간을 의미한다.

struct BIT
{
    int n; vector<int> tree;
    BIT(int n) : n(n), tree(n+10);
    int sum(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
    void update(int i, int val) { for(; i<=n; i+=(i&-i)) tree[i]+=val; }
};

 

1. sum()

$1$~$i$ 까지의 합들을 구해야한다.

주어진 $i$부터 시작해, 마지막 비트를 계속 빼주며 0이될때까지 더해주면 된다.

$i$~$j$ 까지의 누적합이 필요하면, sum() 을 두번 호출한 후 빼주면 된다.

시간복잡도 : $O(logN)$

 

2. update()

$i$번 칸에 $x$를 더하는 연산이다.

주어진 $i$부터 시작해 마지막 비트를 계속 더해주며 $n$이 될때까지 반복하면 된다.

시간복잡도 : $O(logN)$

 

특히 펜윅 트리는 N 차원 자료구조로 사용될 수 있으며 코드도 거의 똑같다.

만약 좌표압축을 할 수 없는 경우 트리의 값들을 map 에 넣어주면 공간복잡도가 줄어드는 대신 시간복잡도가 $logN$ 씩 곱해지게 된다.