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를 많이 쓴다.

  C++11

  * 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