알고리즘 펜윅 트리

시작

펜윅 트리, 세그먼트 트리에서 변형된 형태입니다. 

대표적으로 구간 합 알고리즘을 O(N)보다 빠르게 풀고자 할 때 펜윅 트리를 사용합니다.

일반적으로 구간 합을 구할 때 O(N) 정도의 시간이 걸립니다.

펜윅 트리(BIT = Binary Indexed Tree) 이용하게 되면 O(logN) 으로 시간 복잡도를 감소 시킬 수 있습니다. 

전체 노드의 부분 합 즉, 0~K 합을 구해 두게 되면 원하는 구간 합 S~D를 구하는 것이 가능해 집니다. (Start  ~ Destination)

O(logN) 의 수행시간 만으로 구간합을 구할 수 있게 됩니다. 

구간 합 외에도 같은 원리로 업데이트도 수행할 수 있게 됩니다.

 

펜윅트리 구조

일반적으로 펜윅 트리 구조는 아래와 같이 세그먼트 트리를 응용한 형태로 구조를 정형화 할 수 있습니다. 

그라데이션으로 depth 별 구간을 수정했습니다.

0~7 로 표현한 것은 0부터 7까지 구간 합을 의미합니다. 

또한, X 로 표시된 부분은 펜윅트리의 구조입니다.

세그먼트 트리의 우측 구간을 줄이게 됩니다. 즉, 전체 노드의 1/2씩 줄이게 되는 구조를 가지게 됩니다. 

트리 구조 아래에는

막대 모양으로 도식화 하여 표현한 것입니다. 

구조를 단순화 하기 위해 막대 모양으로 펜윅 트리 알고리즘에 대해 정리해보겠습니다.

step1

펜윅 트리에서 이진수 즉, 비트를 활용하여 이전보다 적은 시간복잡도를 가지게 되므로 

인덱스의 수를 +1 증가시켜 줍니다. 

비트로 값을 계산할 때는 최소 비트가 2의 0승으로 1부터 시작하게 됩니다. 

 

step2

펜윅 트리에서 update를 수행한다고 했을 때 

1을 update 한다고 가정해보면, 1이 포함된 구간을 전부 바라보면 됩니다. 

해당 구간은 step2 그림에서 1, (1~2), (1~4), (1~8) 구간이 됩니다. 

 

step3

이번에는 구간 합에 대해 살펴보겠습니다. 

앞서 작성한 대로

전체 노드의 부분 합 즉, 0~K 합을 구해 두게 되면 원하는 구간 합 S~D를 구하는 것이 가능해 집니다. (Start  ~ Destination)

예시로, step3의 그림에서 1~8에 대해 모든 구간을 표시해 두었고

이 구간에서 3~7 사이의 구간 합을 알고 싶다고 가정하게 되면 

노란색 막대의 합 - 빨간색 막대의 합으로 구간 합을 정의할 수 있습니다. 

(3~7이 들어가 있는 막대의 구간의 위치 = 노란색, 3~7을 제외한 값이 들어가 있는 막대의 구간의 위치 = 빨간색)

step4

본격적으로, 막대에 표시된 숫자들을 비트로 전환하여 보면 규칙을 찾아볼 수 있습니다. 

각 비트에 대한 값을 구간의 최대 정수를 비트로 전환한것입니다. 

이유는 규칙을 찾아서 

우리가 찾고자 하는 3~7 구간의 합의 경우에 

4는 이진수로 100

6은 이진수로 110

7은 이진수로 111 

정의합니다. 

이 연속된 비트들을 잘보면 가장 큰 값 7에서 4까지 비트를 비교해보면 가장 오른쪽 비트 1을 한나씩 빼주게 됩니다. 

step5

step5의 경우는 update에 대한 케이스로

막대 구간에 update 해야할 숫자가 포함되어 있는 경우 노란색 막대가 그 예입니다.

코드

백준에서 2042 구간합 구하기 문제가 세그먼트 트리로도 해결할 수 있지만 펜윅 트리로 문제를 해결할 수 있는 좋은 문제입니다.

Java 언어로 알고리즘을 해결하고 있는데, 완전히 객체지향으로 알고리즘 코드를 짜신분이 있어 참고 하였습니다.

문제에 대해 언급을 하자면 앞서 그림으로 표현했듯이 

문제를 해결하는데 구현이 필요한 요소는 sum, update 부분 입니다. 

이 부분을 구현하기 위해 해당 숫자가 속한 범위를 알아야 하는데

코드상에서

sum인 경우 
i-=(i & -i)
update의 경우
i+=(i&-1)

로 비트 처리를 하게 됩니다. 

import java.util.*;
import java.io.*;

public class Main {

	static long[] arr;
	static Ftree ft;
	private static class Ftree{
		long[] FtreeArr;
		
		Ftree(int length){
			FtreeArr = new long[length];
		}
		
		void update(int idx, long num) {
			while(idx<FtreeArr.length) {
				FtreeArr[idx]+=num;
				idx+=(idx & -idx);
			}
		}
		long sum(int idx) {
			long sum = 0;
			while(idx>0) {
				sum+=FtreeArr[idx];
				idx-=(idx & -idx);
			}
			return sum;
		}
	}
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		int N = stoi(st.nextToken());
		int M = stoi(st.nextToken());
		int K = stoi(st.nextToken());
		
		arr = new long[N+1];
		ft = new Ftree(N+1);
		
		for(int i=1; i<=N; i++) {
			arr[i] = stol(br.readLine());
			ft.update(i, arr[i]);
		}
		
		for(int i=1; i<=M+K; i++) {
			st = new StringTokenizer(br.readLine());
			if(stoi(st.nextToken())==1) {
				int idx = stoi(st.nextToken());
				long updateInput = stol(st.nextToken());
				ft.update(idx, updateInput-arr[idx]);
				arr[idx] = updateInput;
			}else {
				int left = stoi(st.nextToken());
				int right = stoi(st.nextToken());
				sb.append(ft.sum(right)-ft.sum(left-1)+"\n");
				
			}
		}
		
		System.out.println(sb.toString());
		
	}

	private static int stoi(String str) {
		return Integer.parseInt(str);
	}
	private static long stol(String str) {
		return Long.parseLong(str);
	}
}