[자료구조] Fenwick Tree(Binary Indexed Tree)

펜윅 트리(Fenwick Tree) == BIT(Binary Indexed Tree)

- 구간합을 구할 때 log(n)정도의 복잡도를 가지고 있다.

구현을 하기 위해서는 입력받은 값의 2진수에서 처음 1이 나오는 곳의 값을 알아야 한다.

예를 들어서 5의 2진수는 101 이고 처음 1이 나오는 곳의 값은 1이다.

또 다른 예.

3 == 11    -> 1

4 == 100   -> 4

7 == 111   -> 1

12 == 1100-> 4

이렇게 N개를 받은 배열을 A[N]이라고 치면 L[N]은 A의 원소들마다 처음 1이 나오는 곳의 값이다.

또, Tree[i]는 A[i] 부터 앞으로 L[i]개의 합을 저장해놓았다.

L[i]를 구하기 위해서는 아래의 공식이 적용된다.

L[i] = (i & -i);

왜냐하면, 아래의 예시를 보자.

      -num = ~num + 1
       num = 100110101110101100000000000
      ~num = 011001010001010011111111111
      -num = 011001010001010100000000000
num & -num = 000000000000000100000000000

~num은 num의 1의 보수고, +1한게 2의 보수인데 AND를 했을 때 처음 1이 나오는 곳의 값을 얻을 수 있다.

그럼 Tree배열을 사용해서 어떻게 구간합을 구하냐면, 앞서 말했듯이 Tree배열은 A[i]부터 앞으로 L[i]개의 합을 저장해놓았다.

Tree[i]     = A[i] + A[i + 1] + ... + A[i + L[i] - 1]

Tree[i - k - 1] =A[i - k - 1] + A[i - k] + ... + A[i - k - 1 + L[i] - 1]

Tree[i] - Tree[i - k - 1] =  A[i - k] + A[i - k + 1] + ... + A[i + L[i] - 1]

즉, i까지 합 - (k - 1)까지 합 = k부터 i까지의 합 이기때문에 빼주기만 하면 된다.