20. 펜윅 트리 (Fenwick tre, c++)

펜윅 트리 (Fenwick tree)?

펜윅 트리 또는 Binary indexed tree는 prefix sum array의 변형으로 볼 수 있습니다.

 

이 자료구조는 구간의 합을 구하는 연산과 배열의 값을 변경하는 연산을 각각 O(logN)에 처리할 수 있습니다.

 

펜윅 트리의 이점은 구간의 합을 구하는 쿼리 중에도 효과적으로 배열의 값을 변경할 수 있다는 것이고 이 것은 일반적인 prefix sum array로는 처리하지 못합니다.

---

구조

tree라는 이름에서 알 수 있듯이 1차원 배열로 쉽게 표현할 수 있습니다.

 

구현의 용이성을 위해 펜윅 트리에서는 배열의 인덱스를 0이 아닌 1부터 시작합니다.

 

k는 배열의 인덱스입니다.

 

p(k)를 k를 나누는 가장 큰 2의 거듭제곱으로 정의합니다. 이진수에서 가장 우측에 존재하는 1의 위치를 구하는 것과 같습니다.

 

4는 이진수로 100 이므로 p(k)=4 이고 7은 111이므로 p(k)=1 입니다.

k	1	2	3	4	5	6	7	8	9
p(k)	1	2	1	4	0	2	1	4	1

 

p(k)는 값을 저장할 구간의 갯수를 의미합니다.

 

tree[k]에는 k-p(k)+1 부터 k 까지 구간의 합계를 저장합니다.

k	1	2	3	4	5	6	7	8	9
tree[k]	1~1	1~2	3~3	1~4	5~5	5~6	7~7	1~8	9~9

 

이 트리 구조를 이용해 1~k 까지의 합계를 구하는 것은 O(logN)에 수행됩니다.

 

왜냐하면, 1~k 까지의 범위는 합계를 저장한 방식 그대로 O(logN) 범위로 분할할 수 있기 때문입니다.

 

k가 대표하는 구간인 p(k) 만큼 구간을 줄여가면서 1까지 합계를 더하면 됩니다.

 

예를 들어 1~7 까지의 구간합을 구한다면 p(7) = 1, 즉 1개의 구간을 대표하므로 tree[7]의 값에 1~6까지 구간의 합을 더합니다.

 

같은 방식으로 p(6) = 2, 즉 2개의 구간을 대표하므로 tree[6]의 값에 1~4까지 구간의 합을 더합니다.

 

마지막으로 p(4) = 4, 즉 4개의 구간을 대표하므로 최종적으로 tree[7]+tree[6]+tree[4]를 더하면 1~7까지의 합계를 구할 수 있습니다.

 

만약 start~end 까지의 구간합을 구한다면 prefix sum array와 같은 방식으로 sum(1, end)-sum(1, start-1)로 두번의 O(logN)연산으로 구간의 합을 구할 수 있습니다.

 

값을 업데이트 하는 과정도 비슷한 과정으로 O(logN)에 수행되는데, 전체 구간에 대해서 자신의 값이 구간에 포함되는 곳에 모두 업데이트를 하는 방식으로 수행됩니다.

 

3번 index의 값이 바뀌었다면 tree[3]을 업데이트하고 p(3)만큼을 더한 tree[4], 그리고 p(4)만큼을 더한 tree[8]에 업데이트를 수행합니다.

---

Implementation

p(k)는 이진수의 가장 우측에 존재하는 1의 위치를 찾는 연산입니다.

 

이것은 비트연산으로 구할 수 있습니다.

p(k) = k&-k

 

k의 -k는 2의 보수로 비트 반전 후 1을 더한 값과 같고 k과 -k 를 &연산하면 가장 오른쪽에 있는 1만 제외하고 나머지 비트는 모두 0이됩니다.

 

예를 들어 k = 10 이라면 이진수로 1010 이고, -k는 111...110110 이므로 &연산 후 2번째 비트만 1이 되므로 p(10)은 2입니다.

 

k번째 인덱스의 값을 업데이트 하는 연산은 아래와 같이 구현할 수 있습니다.

 

N의 범위를 초과하지 않는 선에서 k가 포함되는 모든 구간을 val 만큼 변화시킵니다.

 

k가 포함되는 모든 구간은 k&-k 씩 증가시키면 구할 수 있습니다.

int update(int k, int val, vector<int>& tree) {
    while (k <= N) {
        tree[k] += val;
        k += k&-k;
    }
    return 0;
}

 

1~k번째 구간의 구간 합을 구하는 연산은 아래와 같이 구현할 수 있습니다.

 

k가 1이 될 때 까지 k&-k 씩 감소시키면서 tree[k]의 값을 더합니다.

int sum(int k, vector<int>& tree) {
    int s = 0;
    while (k >= 1) {
        s += tree[k];
        k -= k&-k;
    }
    return s;
}