펜윅 트리(Fenwick tree, Binary Indexed Tree)

변경되는 데이터 속에서 구간 합을 구하거나 최대/최소, 구간 곱 등을 구할 때 세그먼트 트리(링크)를 사용하였다.

 

하지만 세그먼트 트리는 N개의 배열이 있을 때 4*N개의 공간을 할당해야했기 때문에 많은 메모리를 필요로 하였다.

 

세그먼트 트리와 비슷한 역할을 하면서 N개의 공간을 사용하는 자료 구조가 있다면..?

 

그렇다.

 

그것이 바로 펜윅 트리이다.

 

펜윅 트리

 

펜윅 트리 또는 Binary Indexed Tree(BIT)라고 부른다.

 

Binary Indexed Tree라는 이름에서 알 수 있듯이 인덱스로 이진수를 사용한다.

 

이것이 무슨 말이냐 하면, (그림 출처)

 

펜윅 트리의 구현을 나타낸 그림

n = 16인 위와 같은 배열이 있다고 가정하면,

 

각각의 수가 2진수로 나타냈을 때 어디에 마지막 1이 있는지를 알아야 한다.

 

1 = 0001(2)

2 = 0010(2)

3 = 0011(2)

4 = 0100(2)

...

16 = 10000(2)

 

만약 마지막 1이 있는 위치를 나타내는 수를 L(x)라고 한다면, L(1) = 1, L(2) = 2, L(3) = 1, L(4) = 4,,,L(16) = 16이 될 것이다. 해당 수가 구간에 포함된 숫자의 개수이다. L(3)은 1이니까 [3]의 구간을 나타내고, L(4) = [1, 2, 3, 4], L(16) = [1:16]이다.

 

L[i] 는 i & -i 의 비트 연산으로 구할 수 있는데, 왜냐하면 -i = ~i+1이기 때문에 1들 중 가장 낮은 자리에 있는 1을 반환하게 된다.

 

 

-num = ~num + 1

num = 100110101110101100000000000

~num = 011001010001010011111111111

-num = 011001010001010100000000000

num & -num = 000000000000000100000000000 = L(num)

 

 

 

펜윅 트리를 이용한 합 구하기

만약 [1:13]에 있는 수들의 합을 구하고 싶다면, tree[8](1~8) + tree[12](9~12) + tree[13](13) 을 더해주면 된다. 이러한 합은

 

13을 이진수로 표현했을 때 1101(2) => 맨 뒤에서부터 1을 하나씩 없애주면서 더해주면 되는 것을 알 수 있다.

 

13( =1101(2)) + 12 (=1100(2)) + 8(1000(2))

 

이러한 합은 코드로는 아래와 같이 간단하게 구현된다.

 

int sum(int i){
	int ans = 0;
    while(i>0){
    	ans += tree[i];
        i -= (i & -i);
    }
    
    return ans;
}

 

펜윅 트리의 특성상 1~i 까지의 구간합을 구하도록 함수가 짜져있는데, 만약 [a,b]의 구간합을 구하길 원한다면

[1,b]와 [1, a-1]을 각각 구한 후 이를 빼주면 된다.

 

 

 

값 업데이트 하기

 

펜윅 트리의 값을 업데이트하기 위해서는 해당 인덱스가 어떤 트리에 들어가있는가를 아는 것이 중요합니다.

 

마지막 1 값을 계속 더해나가며 n 범위까지 도달했을 때 끝내주면 됩니다.

 

void update(int i, int num){
	while(i <= n){
    	tree[i] += num;
        i += (i & -i);
	}
}

 

그리고 init(초기화) 함수가 있는 세그먼트 트리와 달리 펜윅 트리에서는 입력 값을 받은 후 해당 값을 인덱스에 업데이트 해주는 방식으로 초기값을 세팅한다.

 

2차원 펜윅 트리

 

2차원 환경에서도 펜윅 트리를 이용한 구현이 가능하다. 우선 2차원의 누적합을 구하는 법을 알아야 한다. 

 

2차원에서의 누적합은 아래의 식으로 표현가능하다.

 

//이 map[n][m] 원래의 배열 값일 때,

prefix[0][0] = map[0][0];

for(int i = 1; i < n; i++)
	prefix[i][0] = prefix[i-1][0] + map[i][0];
    
for(int i = 1; i < m; i++)
	prefix[0][j] = prefix[0][j-1];

for(int i = 1; i < n; i++)
	for(int j = 1; j < m; j++)
		prefix[i][j] = prefix[i][j-1] + prefix[i-1][j] - prefix[i-1][j-1] + arr[i][j];

 

그리고 (left_row, left_col) 에서부터 (right_row,right_col) 범위에 있는 구간 합을 구하고 싶다면

 

prefix[right_row][right_col] - prefix[left_row - 1][right_col] - prefix[right_row][left_col - 1] + prefix[left_row + 1][left_col + 1] 로 구할 수 있다.

 

2차원 펜윅 트리는 아래와 같은 코드로 구현되며, 로우를 차례로 순회하며 각 컬럼에서 1차원 펜윅트리를 수행한다고 생각하면 된다.

 

#include <cstdio>

#define MAX 1024

typedef long long ll;

int n, q;
int map[MAX+1][MAX+1];
ll tree[MAX+1][MAX+1];

ll Sum(int R, int C){
    ll Answer = 0;
    int tmpC;

    while (R > 0){
        tmpC = C;
        while(tmpC > 0){
            Answer += tree[R][tmpC];
            tmpC -= (tmpC) & (-tmpC);
        }
        R -= (R & - R);
    }

    return Answer;
}

ll SumMatrix(int RLeft, int CLeft, int RRight, int CRight){
    return Sum(RRight, CRight) - Sum(RLeft - 1, CRight) - Sum(RRight, CLeft - 1) + Sum(RLeft - 1, CLeft - 1);
}

void Update(int RIndex, int CIndex, ll Value){
    ll diff = Value - SumMatrix(RIndex, CIndex, RIndex, CIndex);
    int tmpC;
    while(RIndex <= n){
        tmpC = CIndex;
        while(tmpC <= n){
            tree[RIndex][tmpC]+= diff;
            tmpC += tmpC & - tmpC;
        }
        RIndex += RIndex & -RIndex;
    }
}