펜윅 트리(Fenwick Tree)

Goal

• 펜윅 트리를 구현할 수 있다.

---

펜윅 트리(Fenwick Tree)란?

펜윅 트리는 구간합을 빠르게 구하기 위한 자료구조이다.

(BIT, binary indexed tree 라고도 한다.)

 

기본 연산

• sum(pos) : [0~pos] 부분합(prefix sum)
  • [a, b]구간의 range sum은 sum(b) - sum(a - 1) 로 구한다.
• add(pos, diff) : 값 변경에 영향 받는 구간 갱신

두 연산 모두 O(logN)의 시간 복잡도를 갖는다.

공간 복잡도 : O(N) - (정확히 N + 1)

 

펜윅 트리 vs 세그먼트 트리

펜윅 트리 장점

• 코드 길이가 더 짧다. (구현이 간단)
• 메모리가 더 적게 든다.

 

세그먼트 트리

• 모든 구간에 대한 값을 가지고 있기 때문에 좀 더 일반적으로 사용이 가능하다. (역 연산이 필요 없음)

 

<참고>

펜윅트리로 최소값 구하기

일반적으로 하나의 펜윅 트리로 RMQ와 같은 질의 연산을 할 수 없다.

그 이유는 생략된 구간을 역 연산을 통해 구하는데, RMQ의 경우 역 연산을 할 수 없기 때문이다.

 

그래서 이 경우 서로 대칭인 두 개의 펜윅 트리를 사용하여 역 연산 없이 RMQ를 구현한다.

 

구간 합 : 더하기의 역 연산인 빼기 연산을 통해 하나의 펜윅 트리로 구현

RMQ : 최대/최소 값 구하는 것의 역 연산이 없기 때문에, 대칭인 두개의 펜윅 트리로 구현

 

펜윅 트리 구조

 

특징

• 펜윅 트리에서는 한쪽 구간(주로 왼쪽)의 값만 저장한다.
• 구간의 오른쪽 끝 값이 모두 다르다.
• 시작 인덱스는 1부터 시작한다. (비트 연산을 위해 필요)
• 비트 연산을 통해 기본 연산(sum, add)을 수행한다.

 

구현 코드

#include <iostream>
#include <vector>

using namespace std;

const int N = 12;
int arr[] = { 1, 9 ,3, 8, 4, 5, 5, 9, 10, 3, 4, 5 };
vector<int> tree(N + 1); // 크기가 고정이므로 미리 할당해도 된다.

int sum(int pos) // 부분합
{
	pos++; // 원본 배열 인덱스가 0부터 시작하는 경우 1을 더한다.

	int ret = 0;

	while (0 < pos)
	{
		ret += tree[pos];
		// 다음 구간을 찾기 위해 최종 비트를 지운다.
		pos &= (pos - 1); // pos -= pos & -pos; 과 동일
	}

	return ret;
}

void add(int pos, int val) // 갱신
{
	pos++; // 원본 배열 인덱스가 0부터 시작하는 경우 1을 더한다.
	while (pos < tree.size())
	{
		tree[pos] += val;
		pos += (pos & -pos); // 상위 구간 인덱스로 갱신
	}
}

int range_sum(int a, int b) // 구간합
{
	return sum(b) - sum(a - 1);
}

int main()
{
	// 펜윅 트리 초기화
	for (int i = 0; i < N; i++)
	{
		add(i, arr[i]);
	}

	// [a,b] 구간 쿼리
	cout << "[0, 11] : " << range_sum(0, 11) << endl;
	cout << "[3, 8] : " << range_sum(3, 8) << endl;

	add(1, 12 - arr[1]); // array[1] : 9 -> 12
	add(3, 1 - arr[3]); // array[3] : 8 -> 1

	cout << "update이후\n";
	cout << "[0, 11] : " << range_sum(0, 11) << endl;
	cout << "[3, 8] : " << range_sum(3, 8) << endl;

	return 0;
}

 

1. 초기화 및 갱신

vector<int> tree(N + 1); // 크기가 고정이므로 미리 할당해도 된다.

void add(int pos, int val) // 갱신
{
	pos++; // 원본 배열 인덱스가 0부터 시작하는 경우 1을 더한다.
	while (pos < tree.size())
	{
		tree[pos] += val;
		pos += (pos & -pos); // 상위 구간 인덱스로 갱신
	}
}

int main()
{
	// 펜윅 트리 초기화
	for (int i = 0; i < N; i++)
	{
		add(i, arr[i]);
	}
}

 

2. 구간 합(range sum / query)

int sum(int pos) // 부분합
{
	pos++; // 원본 배열 인덱스가 0부터 시작하는 경우 1을 더한다.

	int ret = 0;

	while (0 < pos)
	{
		ret += tree[pos];
		// 다음 구간을 찾기 위해 최종 비트를 지운다.
		pos &= (pos - 1); // pos -= pos & -pos; 과 동일
	}

	return ret;
}

int range_sum(int a, int b) // 구간합
{
	return sum(b) - sum(a - 1);
}

 

펜윅 트리 구현 설명

펜윅 트리의 핵심 연산은 비트 연산이다.

비트 단위로 펜윅 트리를 바라보면 다음과 같은 형태를 띈다.

 

• 구간의 오른쪽 끝 값을 통해 구간을 알 수 있다.
• 오른쪽 끝 마지막 비트를 지우면 이전 구간을 구할 수 있다. => 구간합 구할 때 사용
• 오른쪽 끝 마지막 비트를 더하면 상위 포함 구간을 구할 수 있다. => 구간 값 업데이트할 때 사용

 

마지막 비트의 경우 다음과 같은 비트 연산을 통해 구할 수 있다.

(pos & -pos)

 

구간 합 구하기

예를 들어 [5, 15] 구간의 합을 구한다고 해보자

이 구간은 sum[0, 15] - sum[5 - 1] 과 같이 두 개의 부분합(prefix sum)으로 구할 수 있다.

 

• sum[0, 15] = (15) + (14) + (12) + (8) // 괄호는 구간 값을 의미
• sum[4] = (4)

 

그렇다면 sum과 같은 부분합은 어떻게 구할 수 있을까?

1. 현재 구간 값을 더한다. (오른쪽 끝 값을 인덱스로 사용할 수 있음)
2. 이전 구간을 현재 구간으로 설정한다. (오른쪽 끝 마지막 비트를 지워 이전 구간을 구한다.)
3. (1, 2) 왼쪽 끝에 다다를 때까지 반복

while (0 < pos)
{
	ret += tree[pos];
	pos &= (pos - 1); // pos -= pos & -pos; 과 동일
}

 

마지막 비트 지우기

• pos &= (pos - 1) // 지워지는 비트 기준으로 왼쪽은 동일, 나머지는 반전
• pos -= (pos & -pos) // 마지막 비트를 찾고 빼줌

 

구간 값 갱신

예를 들어 배열의 4번째, 즉 트리에서 5번 인덱스를 갱신한다고 해보자.

 

변경 값을 diff 라고 할 때, (5) 를 포함하는 구간 (6), (8), (16)은 diff만큼의 값을 더해줘야 한다.

 

포함 구간의 경우, 오른쪽 끝 마지막 비트를 더해서 구할 수 있다.

ex)

110 = 101 + 1

1000 = 110 + 10

10000 = 1000 + 1000

 

오른쪽 마지막 비트 더하기

• pos += (pos & -pos);

 

References

fenwick vs segment tree

펜윅 트리 - crocus 블로그