펜윅 트리란?(Fenwick Tree, Binary Indexed Tree)

펜윅 트리란 효과적으로 요소를 업데이트하고 수 배열의 구간합을 계산할 수 있는 자료구조 입니다.

세그먼트 트리와 다른점은 오른쪽 자식이 필요없다는 점 입니다.

부모노드와 왼쪽 자식노드의 값을 알고있으면 자연스레 오른쪽 자식노드의 값도 알 수 있기 때문입니다.

펜윅트리를 사용하기위해서 배열을 하나 사용하여 정의할 수 있습니다.

L(i) : i를 2진수로 나타냈을 때 가장 마지막 1이 나타내는 값을 담은 L(i) 를 이용합니다.

십진수를 이진수로 나타낸다음, 이진수로 나타낸 값에서 마지막 1이 나오는 자리 수 의 값이 L(i) 의 값을 의미합니다.

L(i)를 계산하는 방법은 2가지가 있습니다.

첫번째 방법은 위의 방법을 그대로 사용하는 방법입니다. 시간복잡도는 O(logi) 입니다.

두번째 방법은 i & -i 비트연산을 해주는 방법입니다. 시간복잡도는 O(n) 입니다.

-i = ~i + 1과 같기 때문에 i & -i 비트연산을 해주면 마지막 1이 나오는 자리 수를 뽑아올 수 있습니다.

i까지 L(i)개의 합을 Tree[i] 배열을 이용하여 나타낼 수 있습니다.

i 가 12일 경우 L(i) = 4 이고, Tree[12] = A[9] + A[10] + A[11] + A[12] 라고 할 수 있습니다.

펜윅트리는 사실 구간합을 구할 수 없습니다. 첫번째수부터 i번째 수 까지의 합을 구하는 것만 할 수 있습니다.

A[1] 부터 A[13] 까지의 합은 tree[1101(2)] + tree[1100(2)] + tree[1000(2)] 와 같습니다.

그 이유는 다음과 같습니다.

13 = 1101(2) -> L(13) = 1 -> tree[13] = A[13]

12(13 - L(13)) = 1100(2) -> L(12) = 4 -> tree[12] = A[9] + ... + A[12]

8(12-L(12)) = 1000(2) -> L(8) = 8 -> tree[8] = A[1] + ... + A[8]

이를 이용하여 i ~ j 번째까지 구간합을 구할 수 있게 됩니다.

A[1] ~ A[j] 까지 합을 구하고, A[1] ~ A[i-1] 까지의 합을 구하여서 이를 빼주면 됩니다.

(이러한 이유때문에 최소값을 구할 수 없게됩니다.)

이를 코드로 나타내면 아래와 같습니다.

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

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

*쿼리 i~j 까지 구할 때 시간, 공간복잡도

daisy.day()