펜윅 트리(fenwick tree)

펜윅 트리

• 바이너리 인덱스 트리(binary indexed tree)라고도 함
• 2진법 인덱스 구조를 활용해 구간 합 문제를 효과적으로 해결할 수 있음
• 0이 아닌 마지막 비트를 찾는 법 : 특정 숫자 K의 0이 아닌 마지막 비트를 찾기 위해서는 K & -K 계산하면 됨 

  

 

1. 트리 구조 만들기 : 0이 아닌 마지막 비트 = 내가 저장하고 있는 값들의 개수

   

    

2. 업데이트 : 0이 아닌 마지막 비트만큼 더하면서 구간들의 값 변경 (예시 = 3rd)
   3번째 값이 변경되었다면, 3, 4, 8, 16이 3번째 인덱스에 대한 합 정보를 가지고 있는 인덱스이기 때문에 해당 인덱스들의 값을 업데이트 하면 됨
   -> 시간 복잡도가 최악의 경우에도 O(logn)을 보장

   

3. 1부터 N까지 누적합 구하기 : 0이 아닌 마지막 비트만큼 빼면서 구간들의 합 계산
   1-11번째 원소의 누적합 = 11번째 하나의 값을 가지고 있는 인덱스 11의 값 + 9-10번째 값의 합을 가지고 있는 인덱스 10의 값 + 1-8번째 값의 합을 가지고 있는 인덱스 8의 값 
   -> O(logn)의 시간 복잡도 보장 가능
   
   

   

[예시] BOJ 2042 구간 합 구하기

https://www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

 

풀이 코드

// 펜윅 트리
#include <iostream>
#pragma warning(disable:4996)
using namespace std;

long long arr[1000001], tree[1000001];
int n, m, k;

// i번째 수까지의 합 구하는 함수
long long prefixSum(int i) {
	long long result = 0;
	while (i > 0) {
		result += tree[i];
		// 0이아닌 마지막 비트(i & -i)만큼 빼가면서 이동 
		i -= (i & -i);
	}
	return result;
}

// i번째 수에 dif 만큼 더하는 함수
void update(int i, long long dif) {
	while (i <= n) {
		tree[i] += dif;
		i += (i & -i);
	}
}

// start부터 end까지의 구간 합 계산
long long intervalSum(int start, int end) {
	return prefixSum(end) - prefixSum(start - 1);
}

int main() {
	scanf("%d %d %d", &n, &m, &k);
	for (int i = 1; i <= n; i++) {
		long long x;
		scanf("%lld", &x);
		arr[i] = x;
		update(i, x);
	}
	int count = 0;
	while (count++ < m + k) {
		int op;
		scanf("%d", &op);
		// 업데이트 연산일 경우
		if (op == 1) {
			int index;
			long long value;
			scanf("%d %lld", &index, &value);
			update(index, value - arr[index]); // 바뀐 크기만큼 적용
			arr[index] = value;
		}
		// 구간 합 연산일 경우
		else {
			int start, end;
			scanf("%d %d", &start, &end);
			printf("%lld\n", intervalSum(start, end));
		}
	}
	return 0;
}

 

 

 

 

 

 

 

출처 : https://www.youtube.com/watch?v=fg2iGP4e2mc