Binary Indexed Tree와 구간의 사용방법

이것이 Binary Indexed Tree이다.
Binary - 이진의
Indexed - 인덱스가 매겨진
Tree - 트리
(용어의 정의에는 사람마다 차이가 있다.)

위의 BIT 그림에서, 가장 밑의 줄에 7개의 원소를 쓰려고 한다면?
8부터 14까지의 원소를 각각 첫번째부터 7번째까지로 사용하면 된다.
그리고, 7보다 크면서 가장 작은 2의 제곱수는 8이다.

즉 n개의 원소를 가장 밑줄에 쓰려고 한다면,
n 이상이면서 가장 작은 2의 제곱수를 m이라고 하고,
m부터 m+n-1까지의 원소를 사용하면 된다.
그렇다면 배열로 선언할때는 m+n-1까지의 배열을 선언하면 된다.
일반적으로는 2m-1까지의 배열을 잡는다.

각 노드의 부모와 자식의 관계를 살펴보면

부모	2	5	n
왼쪽 자식	4	10	2n
오른쪽 자식	5	11	2n+1

임의의 구간에 대해서 어떤 작업을 처리할 때, 그 구간의 원소들 중 일부가 한 노드에 포함된다면, 그 노드에 대해서만 작업을 처리하면 된다.
그를 위해, 각 노드의 자식들의 값을 가지고 문제에 맞는 과정을 통해서 그 부모의 값을 정해주면 된다.

예를 들어, 하나의 수열이 있고, 쿼리가 들어온다고 치자.
A x y 라는 쿼리는 x번 위치의 값을 y로 바꾸고,
B x y 이라는 쿼리는 x부터 y까지의 구간에서의 최댓값을 구하는 쿼리라고 하자.

이걸 그대로 구현한다면,
A x y 는 data[x]=y 를 수행하고,
B x y 는 data[x]~data[y]를 모두 돌면서 최댓값을 구하면 된다.
그렇다면, A쿼리는 \(O(1)\), B쿼리는 \(O(N)\)이 걸린다.
B 종류의 쿼리가 많이 들어오고, \(N\)이 충분히 크다면 시간 내에 수행하기 어렵다.

이때 BIT를 사용한다.
B 1 6이 들어왔다고 하자.
1부터 6까지의 구간은, 각각 8,9,10,11,12,13이 대표하고 있고,
간단하게 줄이면 2,6이 대표하고 있는 것과 같다.
그러면 트리의 [2]번 노드와 [6]번 노드의 최댓값만 확인해주면 된다.
여기서 2와 6이라는, 구간을 대표하는 숫자를 구하는 방법을 생각해보자.

먼저, \(left\)와 \(right\)를 정한다. 여기서는 \(8\)과 \(13\)이다.
답을 저장할 변수를 임의로 \(ans\)라고 하겠다.

매 단계마다, \(left\)와 \(right\)를 \(2\)로 나눠준다(부모로 이동).
이 상태에서는, \(left\)가 \(4\), \(right\)가 \(6\)이 되면 원래 구간과 동일하다.

\(left=4, right=6\)

여기서, 또 다시 \(left\)와 \(right\)를 \(2\)로 나누려고 하면,
\(right\)가 \(3\)이 되어버려 다른 구간을 나타내게 된다.
즉 \(6\)의 경우에는, 그 윗쪽 노드로는 \(6\)이 의미하는 구간을 표현할 수 없다는 의미이다.
그러면 ans에 ans와 \([6]\)의 최댓값을 저장하고,
왼쪽으로 한 칸 간다(\(right=5)\)).
이제 \(left\)와 \(right\)를 \(2\)로 나누면 \(left=2, right=2\).

이제 \(left=right\)가 되어 2밖에 남지 않았으므로, ans에 ans와 \([2]\)의 최댓값을 저장하고 끝낸다.
GIF로 나타내보면.

알고리즘을 대략 설명하면
1) 매 단계에서 left/=2, right/=2를 해준다.
2) left==right이면 left를 체크하고 break해준다.
3) left>right가 되는 경우에도 break를 해준다.
4) right가 부모의 왼쪽 자식이면 체크하고 왼쪽으로 한 칸 넘어간다.
5) left가 부모의 오른쪽 자식이면 체크하고 오른쪽으로 한 칸 넘어간다.

코드로는

while(left<=right)
{
    if(left==right){
        check(left); // check(right)도 상관 없음
        break;
    }
    if(left%2==1)
    {
        check(left);
        left++;
    }
    if(right%2==0)
    {
        check(right);
        right--;
    }
    left/=2; right/=2;
}

check 함수는 필요한 대로 구현하면 된다.

참고로 left/=right/=2 라고 쓰면, left/=(right/2)가 되어, 제대로 작동하지 않는다. 코드를 줄이려고 저렇게 쓰지는 말자.

연습문제

koistudy 0579(1401): Range Minimum Query