[알고리즘] 펜윅트리

이희수·2024년 7월 29일

C++알고리즘 펜윅트리

알고리즘

목록 보기

18/25

펜윅트리

펜윅트리는 이진 트리기반의 자료구조이며 세그먼트 트리의 원리를 가지고 있다.

세그먼트 트리

아래는 최솟값의 index를 담은 트리이다.

이처럼 세그먼트 트리는
1. 이진트리에
2. 어떤 쿼리에 대한 최적화한 값을 담아놓은 것을 의미한다.

이를 이용하여 최솟값을 탐색한다면 쉽게 O(logN)만에 찾을 수 있다.

문제를 풀 때 어떠한 구간에 대한 구간 쿼리를 표현할 때 시간복잡도가 많으니 안될 것 같다, O(logN)짜리의 알고리즘이 필요하다. 할 때 이 알고리즘을 생각해보자.

이러한 세그먼트 트리의 특징이 담긴 펜윅트리이다.

세그먼트 트리와 달리 모든 세그먼트를 만들 필요가 없으며, 이진트리 인덱스를 효율적으로 계산 및 업데이트 할 수 있는 자료구조를 말한다.

펜윅트리 구조

16칸의 펜윅트리이다.
빨간 숫자는 펜윅트리의 Index를 의미하고 제일 윗칸은 실제 배열(A)의 Index를 의미한다.

예를들어 12번 인덱스는 9-12, 즉 A[9]+A[10]+A[11]+A[12] 이다.

각 Index를 2진수로 나타내면 다음과 같다.

'2'는 0010(2) 이고 1이 존재하는 최하위 비트는 '2'이다. 2번 Index는 2번부터 앞으로 2칸까지의 구간연산 결과값인 1번 A[1]+A[2] 값을 가지고 있다.

'4'는 0100(2) 이고 '1이 존재하는 최하위 비트'는 '4'이다. 4번 Index는 4번부터 앞으로 4칸까지의 구간연산 결과값인 A[1]+A[2]+A[3]+A[4] 값을 가지고 있다.

'12'는 1100(2) 이고, '1이 존재하는 최하위 비트'는 '4'이다. 12번 Index는 12번부터 앞으로 4칸 까지의 구간연산 결과값인 A[9]+A[10]+A[11]+A[12] 값을 가지고 있다.

이로써 아래와 같은 규칙을 발견할 수 있다.

1. 펜윅트리는 비트를 이용해서 생성된다.
2. 각 Index를 2진수로 표현했을 때, '1'이 존재하는 가장 최하위 비트의 값(x) 을 찾는다
3. 해당 Index부터 x칸 앞까지의 구간연산에 대한 결과값을 가진다.

펜윅트리 구현방법

그렇다면 꽤 어려워보이는 펜윅트리를 어떻게 구현할 수 있을까?

Update(갱신)

초기 펜윅트리에 모든 인덱스들이 '0'으로 초기화 되어있고, N만큼의 공간만 할당되어있는 상태이다.

가장 먼저 A[1] = 1의 값을 할당하는 과정을 살펴보자.

먼저 보기 쉽게, A[1]에 의해서 영향을 미치게 되는 노드들을 색깔로 칠하면 아래와 같다.

이를 비트로 표현해보면

1 = 0001(2)
2 = 0010(2)
4 = 0100(2)
8 = 1000(2)
16 = 10000(2)

규칙이 보이는가?
현재 Index의 '1'이 있는 최하위 비트를 찾아서 '1'을 더해주면 다음번 Index가 나온다!

이를 확인하기 위해 A[9] = 9의 값을 할당하는 과정을 살펴보자.

A[9]에 의해서 영향을 미치게 되는 노드들을 색깔로 칠하면 아래와 같다.

9 = 1001(2)
10 = 1010(2)
12 = 1100(2)
16 = 10000(2)

이번에도 찾은 규칙이 성립하는 것을 확인할 수 있다.

그렇다면 '1'이 있는 최하위 비트를 어떻게 찾아서 1을 더해줄 수 있을까?

공식은 아래와 같다.

Index += (Index & -Index)

-Index는 Index의 보수(현재 값을 뒤집은 후에 1을 더한 값) 이므로 &(and) 연산을 해준후 원래 Index에 더해주면 되는것이다.

즉, 1001(2)에 대한 보수값: 0111(2)
1001 + (1001 & 0111) = 1001 + 0001 = 1010

위 성질을 이용하여 펜윅트리의 원소를 갱신해주는 Update를 아래와 같이 구현할 수 있다.

void update(vector<int> &tree ,int i ,int value){
	while(i < tree.size()){
		tree[i] += value;
		i += (i & -i);
	}
}

Sum(구간에 대한 연산)

예를 들어 1번~7번 Index까지의 합을 구하는 경우를 살펴보자.
1번~7번 Index까지의 합을 구하기 위해서는 다음 노드들을 계산해줘야 한다.

그럼 어떻게하면 7 -> 6 -> 4로 이동하면서 더해줄 수 있을까?

이번에도 2진수로 표현해보자.

7 = 0111(2)
6 = 0110(2)
4 = 0100(2)

이번에는 신기하게도 현재 Index의 '1'이 있는 최하위 비트를 찾아서 '1'을 빼주면 다음번 Index가 나오는 것을 확인할 수 있다.

Index -= (Index & -Index)

하지만 이는 7번 Index까지의 누적합이다.
부분합은 어떻게 구해야할까?

3번 ~ 7번 Index의 합을 구하는 연산으로 바꿔보자.

이는 파란색 노드들을 모두 더하고 노랑색 노드만큼을 빼줌으로서 구할 수 있다.

즉, 펜윅트리에서 A번 Index부터 B번 Index 까지의 부분합을 구하려면 B번 Index까지의 누적합 - A-1번 Index까지의 누적합을 구해주어야 한다.

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

문제를 통해 더 알아보자.

백준 2042 구간합 구하기

2042 구간합 구하기

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
int n,m,k,a,b,c;
ll d;
void update(vector<ll> &tree, int i, ll value){
	while(i<tree.size()){
		tree[i] += value;
		i += (i & -i);
	}
}
ll sum(vector<ll> &tree, int i){
	ll result = 0;
	while(i>0){
		result += tree[i];
		i -= (i & -i);
	}
	return result;
}
int main(){
	cin>>n>>m>>k;
	// 원소를 담을 vector
	vector<ll> arr(n+1);
	// 구간합 펜윅트리 
	vector<ll> tree(n+1);
	// 1번 Index 부터 시작해야 함 
	for(int i=1; i<=n; i++){
		cin>>arr[i];
		update(tree,i,arr[i]);
	}
	for(int i=0; i<m+k; i++){
		cin>>a;
		if(a == 1){
			cin>>b>>d; 
			// 바꾸려는 차이만큼 갱신 
			ll diff = d-arr[b];
			arr[b]=d;
			update(tree,b,diff);
		}
		else{
			cin>>b>>c;
			cout<<sum(tree,c)-sum(tree,b-1)<<"\n";
		}
	}
}