블로그 이사 중입니다 >> gumgood.github.io
Fenwick Tree, BIT 본문
Fenwick Tree : *부분합을 빠르게 계산하면 구간합도 계산할 수 있음을 이용한 구간합 tree
BIT(Binary Indexed Tree)라고 부르기도 한다.
(*부분합 psum[pos] : 배열의 첫 부분부터 연속된 합 (A[0] + A[1] + ... + A[pos]))
구간합 [i, j]는 psum[j] = psum[i-1]으로 쉽게 구할 수 있다.
* 여기 종만북과 비슷한 설명이 잘 되어있다.
* Seg-tree보다 간단하고 빠르고 메모리 적게 먹음.
1. Fenwick Tree와 Segment Tree
Segment tree에서 [0, 15] node의 자손으로 [0, 7], [8, 15] node가 있는데, 사실상 [0, 7]을 알면 [8, 15]의 node는 필요가 없다.
Seg-tree의 불필요한 node를 제거한 것이 Fenwick Tree의 틀이다.
메모리 : Seg-tree , Fenwick tree
수행시간 : Seg-tree > Fenwick tree (시간복잡도는 같지만, Fenwick tree가 더 빠르다)
구현 : Fenwick tree가 간단하다.
2. Fenwick Tree 구현
위의 그림으로부터 다음 배열을 정의한다. (구간의 시작위치는 그림을 참고)
tree[i] := 위의 그림에서 오른쪽 끝 위치가 A[i]인 구간의 합
2.1 query : 부분합 psum[pos] 계산하기
tree[pos]를 포함하여 구간에서 남은 부분들을 왼쪽에서 찾아 더한다.
tree배열의 index를 binary number로 봤을 때, 더해야하는 구간의 힌트를 얻을 수 있다.
Hint는, pos의 마지막 bit를 지우면 tree[pos] 다음 더해야할 구간이 나오게 된다.
이는 bitwise를 이용해 연산가능하다. (pos -= (pos & -pos), 왜인지는 생각해보자)
이렇게 부분합을 구하면, 구간합을 구한 것과 마찬가지이다.
2.2 update : a[i]의 값을 갱신
query 연산과 마찬가지로 tree 배열의 index의 패턴을 이용해야 한다. (모르겠으면 종만북)
결론은 binary number의 마지막 bit값(ex, 1010 -> 10)을 더하면
갱신해야할 다음 구간의 index가 된다. (놀라워라!)
이 bit연산 때문에 소스가 seg-tree에 비해 짧다.
때문에 계속 변하는 배열의 구간합을 구하는 문제에서는 seg-tree보다는 Fenwick tree를 많이 쓴다.
* update()는 a[i]를 diff로 갱신한다. 갱신하는 어떤 연산(대입, 덧셈,max, ..)인지 정확히 파악하여 구현하자.
3. Fenwick Tree 시간복잡도
query(), update() 두 연산은 각 loop문을 돌 때마다 tree의 한 층을 올라가므로
tree의 높이 에 비례한다. 따라서, 시간복잡도는
이 된다.
실제 두 함수는 필요한 구간만을 개 이하로 접근하기 때문에 seg-tree의 불필요한 구간(메모리), 연산 등이 생략되어 빠르게 작동한다.
'Problem Solving > 분류없음' 카테고리의 다른 글
Range Queries와 Modifications over Array의 Non-recursive 구현 (0) | 2019.04.17 |
---|---|
Binary search algorithm - detail (2) | 2019.04.04 |
Fenwick Tree, BIT (0) | 2017.05.27 |
Minimum Spanning Tree (0) | 2017.05.27 |
Longest Increasing Subsequence (0) | 2017.05.27 |
Segment Tree (구간 트리) (0) | 2017.05.27 |
- Tag
- Fenwick Tree