[자료구조] 펜윅 트리 (Fenwick Tree) - Binary Indexed Tree
Algorithm/Data Structure 2023. 12. 6.
반응형
목 차
- 펜윅 트리(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
}
}
반응형
'Algorithm > Data Structure' 카테고리의 다른 글
[자료구조] 세그먼트 트리 (Segment Tree) (0) | 2023.11.21 |
---|---|
[자료구조] 우선순위 큐(Priority Queue) (0) | 2023.10.26 |
[자료구조] Union Find / Disjoint-Set 알고리즘 개념 및 최적화 (0) | 2023.10.16 |