[자료구조] 펜윅 트리 (Fenwick Tree) - Binary Indexed Tree

 목  차

• 펜윅 트리(Fenwick Tree)
• 펜윅 트리와 세그먼트 트리
• 펜윅 트리를 구현하며 배운 것들
• 구현 방법

 

 

 

---

 

 

  펜윅 트리(Fenwick Tree)

 

Binary Indexed Tree 라고도 불리는 펜윅트리는 수열의 특정 구간의 합을 빠르게 계산하고, 요소를 빠르게 변경 할 수 있는 자료구조 이다.

 

 

  특징

 

시간 복잡도: update 와 sum 메서드 모두 O(log n)의 시간 복잡도를 가진다.

공간 복잡도: O(n) 만큼의 공간을 사용한다.

 

 

   작동 원리

 

SUM 함수: 구간 합을 구하는 함수

UPDATE 함수: 특정 요소가 변경되면 그 요소에 영향을 받는 인덱스를 타고 올라가며 변경한다.

 

 

 

---

 

 

  펜윅 트리와 세그먼트 트리

 

	세그먼트 트리	펜윅 트리
구조	이진 트리 기반	배열 기반
시간 복잡도	업데이트 & 구간 합 모두 O(log n)	업데이트 & 구간 합 모두 O(log n)
공간 복잡도	O(4n)	O(n)
구현 난이도	상대적으로 복잡	상대적으로 간단

 

 

 

---

 

 

  펜윅트리를 구현하며 배운 것들

 

 

2의 보수

 

컴퓨터에서 음수를 표현하는 방식이다. 2의 보수를 구하는 방법은 비트를 반전시키고 1을 더한다.

예를 들어, 5를 2의 보수로 구해보자면, 5의 2진 표현은 101이다.

• 비트 반전: 모든 1을 0으로, 0을 1로 바꿈
  • 결괏값: 010
• 1을 더함: 비트 반전 후 1을 더한다.
  • 결괏값: 011

여기서 011은 10진수에서 3을 나타내기도 하지만,

• 부호 비트가 0일 때: 나머지 비트는 해당 숫자의 절대값을 2진수로 나타낸다.
• 부호 비트가 1일 때: 나머지 비트는 숫자의 2의 보수를 2진수로 나타낸다.

위에서 설명한 5를 예로 들자면, 101(2진수)과 011(2의 보수)인데, 여기서 5 & -5 연산을 한다면 2^0인 1이 나온다.

펜윅트리에서는 5번 인덱스의 구간의 크기가 1이 라는 의미가 된다.

 

 

 

  LSB(Lowest Significant Bit) - 최하위 유효 비트

 

2진수에서 가장 오른쪽에 위치한 비트를 말한다.

즉, LSB는 2^0 자리를 의미하는데, LSB가 1이면 홀수, 0이면 짝수이다.

 

 

 

---

 

 

  구현 방법

 

update 메서드:

• 인자: x, diff
  • // x: updated index, diff: 원래 값과 새로운 값의 차이
• 조건: x ≤ n
• 동작: x 에서 x & -x 를 더해주면 해당 인덱스가 영향을 주는 다음 인덱스를 찾아갈 수 있다.

 

sum 메서드:

• 인자: x
  • // x: index
• 조건: x > 0
• 동작: x에서 x & -x를 빼주고 반복하면 1 부터 x 까지의 합을 구할 수 있다.

 

구간합:

a 와 b 의 구간합을 구하고 싶다면, sum(b) - sum(a - 1) 을 하면 가능하다.

 

 

class FenwickTree {
	// N: 요소 개수
	constructor(N){
		this.N = N;
		this.tree = new BigInt64Array(this.N+1).fill(0n)
  }

	// index: 변경 된 인덱스, diff: 원래 값과 현재 값의 차이
	update(index, diff){
		while(index <= this.N){
			this.tree[index] += BigInt(diff);
			index += index & -index;
		}
	}

	// sum 메서드: 1부터 index 까지의 합을 구하고 반환함
	sum(index){
		let result = 0n;
		while(index > 0){
			result += this.tree[index];
			index -= index & -index;
		}
		return result
	}
}