Binary Index Tree(BIT, Fenwick Tree)

# 아래 링크의 글에 보충 설명을 더한 글입니다. 먼저 아래 글을 읽고 이해가 잘 안 되신다면 보는 걸 추천드려요

https://www.acmicpc.net/blog/view/21

펜윅 트리 (바이너리 인덱스 트리)

 

Binary Index Tree의 정의는 wiki에 가서 찾아보는게 더 좋을 것이다.

 

BIT의 필요성

 

BIT란 쉽게 말해 빠른 속도로 구간 합을 구할 수 있게 도와주는 자료구조이다.

이는 Tree를 생성하는데 O(logN), 구간합을 구하는데 O(logN) 시간이 소요된다.

 

이렇게 접근하면 이해가 잘 안될 수 있으니 문제로 살펴보자.

https://www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

백준 2042번 구간 합 구하기 문제이다.

 

일반적으로 구간 합을 구하는 문제에서 나 포함 알린이들은 Prefix Sum을 사용할 것이다.

 

일반적인 구간 합 문제는 당연히 Prefix Sum으로 해결이 가능하다.

이 알고리즘은 O(N) 시간안에 답을 구할 수 있게 해 준다.

 

그럼 저 문제도 Prefix Sum으로 구할 수 있을까?

 

N 제한만 보면 100만이기 때문에 되는 거 아닌가?라고 생각할 수 있지만 문제를 보면 매번 데이터의 변화가 생긴다. 

 

Prefix Sum은 배열이 고정되어있을 때 O(N) 시간 안에 구할 수 있다.

그렇다면 이 문제에서 K번만큼 변한다고 하였으므로 매번 Prefix Sum알고리즘을 사용하려면 

시간 복잡도는 O(1000000 * 10000)이 된다. 즉 O(10000000000), 100억의 시간 복잡도를 갖는다.

 

따라서 문제의 시간제한에 부합하지 않는다.

 

바로 이런 경우를 위해 우리는 BIT를 알아야 한다.

 

(갑자기 드는 생각인데 옛날에 코드 포스였는지 카카오 코테였는지 기억은 안 나는데 BIT 문제 나왔던 것 같은데..? 그때 내가 Prefix Sum으로 풀다 포기했었는데 그때도 query 때문에 시간 초과였는데 이거였구나..)

 

BIT 알고리즘

 

본격적으로 BIT 알고리즘에 대해 알아보자.

 

1. L[i]는 i를 2진수로 나타냈을 때, 마지막 1의 위치(가장 오른쪽 1)가 나타내는 값을 저장하고 있는 배열이다.

 

즉 3을 이진수로 나타냈을 때 가장 마지막 1은 2^0=1 이므로 L[3] = 1이다.

이와 마찬가지로 L[5] = 1, L[6] = 2, L[8] = 8, L[9] = 1, L[10] = 2, L[11] = 1, L[12] = 4, L[16] = 16이다.

(나타내는 값이 배열에 들어가야 한다!!)

 

 

2.  Tree[i]는 A[i]로부터 앞으로 L[i]개의 합을 저장하고 있는 배열이다.

 

난 처음에 이 부분이 제일 이해가 안 갔는데 그냥 국어를 못해서였다.. 

 

핵심 포인트는 "앞으로"이다.

 

이해를 돕기 위해 앞에 어떤 것을 나타내는지 추가해보았다.

이제 차근차근 살펴보자.

 

Tree[1] 은 A[1]로부터 앞으로 L[1]개의 합이다. 즉 1개의 합이니까 위와 같다.

Tree[2] 은 A[2]로부터 앞으로 L[2]개의 합이다. 즉 2개의 합이니까 위와 같다.

...

Tree[4] 은 A[4]로부터 앞으로 L[4]개의 합이다. 즉 4개의 합이니까 위와 같다.

,,,

Tree[8] 은 A[8]로부터 앞으로 L[8]개의 합이다. 즉 8개의 합이니까 위와 같다.

 

말 그대로 Tree의 정의에 따라 그려놓은 것이다.

 

 

3. L[i] = i & -i

 

위의 트리를 그리려면 결국 L[i]를 알고 있어야 한다.

그 뜻인즉슨 L[i]를 구하는 시간 역시 시간복잡도에 중요한 영향을 끼친다는 것이다.

 

그럼 L[i]를 어떻게 빠르게 구할까? 

답은 위에 적혀있다.

 

먼저 "&" 연산자는 비트 연산에서 and 연산을 뜻한다는 것을 알고 있어야 한다.

and 연산	1	0
1	1	0
0	0	0

 

이제 여기선 모르는 사람이 있을 수 있지만 현재 우리들의 컴퓨터는 2의 보수 표현법을 사용한다.

???

아래의 링크에 잘 설명되어 있다. (본의 아니게 내 블로그를 홍보해버렸네ㅎㅎ)

https://kimtaehyun98.tistory.com/40?category=982060 

 

이제 우리는 컴퓨터가 내부적으로 2의 보수 표현법을 사용하고 있다는 것을 알았다.

 

그럼 아래의 내용이 이해가 안 될 수가 없다.

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

여기서 ~은 1의 보수를 취한 것이다.

1의 보수를 취한다는 것은 각 비트를 0->1, 1->0로 반전한다는 의미이다.

 

결국 위의 과정을 통해 O(1) 시간만에 L[i]를 구할 수 있게 되었다.

 

 

4. 합 구하기

 

그럼 이제 실전으로 들어가 보자.

 

아래와 같은 BIT를 만들었다고 가정해보자.

위 트리는 L[i]를 생략한 모습이다.

 

그럼 여기서 문제는 합은 어떻게 구해야 할까?

 

예를 들어 A[1] + A[2] + ... A[13]를 구해야 한다고 가정해보자.

 

여기서 다시 기억해내야 하는 사실은 Tree[i]는 A[i]로 부터 앞으로 L[i]개의 합을 저장하고 있다는 점이다.

 

그럼 다시 돌아와서 위의 성질을 사용해보면

 

A[1] + A[2] + ... A[13] = Tree[13] + Prefix Sum[13-L[13]] = Tree[13] + Prefix Sum[12] 이다.

 

왜냐하면 Tree[13]은 A[13]으로 부터 앞으로 L[13] = 1개의 합을 저장하고 있으므로 A[13]과 같기 때문이다.

 

따라서 Prefix Sum[X] = Tree[X] + Prefix Sum[X-L[X]]란 식을 얻어낼 수 있다. (구현에 사용된다.)

 

계속해서 구해보자.

 

Tree[13] + Prefix Sum[12] = Tree[13] + Tree[12] + Prefix Sum[12-L[12]] = Tree[13] + Tree[12] + Prefix Sum[8]이다.

 

Prefix Sum[8] = Tree[8] 이므로 최종적으로 구해야 할 것은 Tree[13] + Tree[12] + Tree[8]이다. 

 

따라서 Prefix Sum[13] = Tree[13] + Tree[12] + Tree[8]이다.

 

 

5. 구현 1 - 합 구하기

 

위의 과정을 그대로 코드로 작성하면 된다.

int sum(int i) {
    int ans = 0;
    while (i > 0) {
        ans += tree[i];
        i -= (i & -i);
    }
    return ans;
}

아주 짧고 간결하다. 이게 과연 고난이도의 알고리즘이 맞는지 의심이 들 정도이다.

 

결국 while문 안의 아래 코드는

ans += tree[i];
i -= (i & -i);

Prefix Sum[X] = Tree[X] + Prefix Sum[X-L[X]]을 그대로 코드로 옮긴 것이다.

 

 

6. 구현 2 - 업데이트(Tree 생성)

 

내가 BIT를 공부하면서 가장 궁금했던 것은 그럼 어떻게 Tree를 만들어 놓지? 였다.

 

애초에 위의 sum 함수도 Tree가 없으면 못 구하는거 아닌가?

 

맞는 말이긴 한데 당연히 만드는 방법이 있었다..

 

Update, 즉 Tree를 바꾸려면 자신이 영향을 끼치는 부분만 바꿔주면 된다.

위 그림을 보면 i를 변경했을 때 어느 부분을 update 해줘야 하는 건지 나와있다.

 

예를 들어 A[3]이 교체된다면 아래의 빨간 동그라미 친 부분들을 update 해주면 된다.

이를 코드로 나타내면 다음과 같다.

void update(int i, int num) {
    while (i <= n) {
        tree[i] += num;
        i += (i & -i);
    }
}

와.. 이거 맞아?

 

i = 3이고 num = 5라 가정해보자.

여기서 살짝 이해가 안 갈 수 있다.

 

tree[3] += num 하면 안 되는 거 아닌가?

맞다. 안된다.

 

실제 구현해서는 위의 num에 들어가는 수가 현재 tree를 처음 생성하는지 or 원래 값을 변경하는지에 따라 달라져야 한다!

 

원래 있던 수를 변경하려면 원래 있던 수와 변경하려는 수의 차이만큼을 update 하면 된다.

 

Tree를 처음 생성할 때는 차이가 아니라 num을 바로 update 하면 된다.

 

이 부분이 헷갈릴 수 있는데 잘 생각해보면 너무 당연하다.

 

7. 시간 복잡도

 

처음에 언급했듯이 합을 구하는데 O(logN), 배열을 채우는데 O(logN) 시간이 걸린다.

 

합 코드를 보면 결국 while문이 시간 복잡도를 좌우하는데 while문의 조건이 i > 0이다.

이때 i -= i & -i 이므로 결국 맨 오른쪽 비트를 하나씩 빼는 것이다.

ex) 1101 => 1100 => 1000

 

이 반복문은 아무리 많이 반복해봤자 최대 비트 수를 넘을 수 없기 때문에 결국 O(logN)을 만족한다.

(예를 들어 log13은 3.~이고 비트로 표현하면 4비트 안에 표현이 되니까)

 

update도 마찬가지이다.

처음 수를 3이라 가정하면 2진수로 11에서 다음으로 자신이 영향을 주는 수는 100(2)이다.

다음은 1000, 10000,... 

결국 이 역시 비트 단위로 증가하기 때문에 O(logN)을 만족한다.

 

 

결론

 

알고만 있으면 놀라운 성능을 자랑한다.

 

아래 링크는 위의 백준 2042번 구간 합 구하기에 대한 코드이다.

https://kimtaehyun98.tistory.com/111

백준 2042번 - 구간 합 구하기