Fenwick tree

Fenwick tree, 펜윅 트리라고 불리는 자료구조가 있다.
binary indexed tree (BIT) 라고도 불린다.

옛날에는 이 BIT라는 이름이, 펜윅 트리 말고
top-down 혹은 bottom-up 형식의 세그먼트 트리를 가리키기도 한 것 같은데,
요즘은 다들 이 펜윅 트리만 지칭하는 것 같다.

각각의 숫자는 인덱스(첨자)를 의미하고, 그 숫자와 연결된 흑색 사각형과 그 밑의 흰색 직사각형이 전부 해당 인덱스가 들고 있는 영역이다.

각각의 숫자가 나타내는 구간이 어떻게 결정되는지 알아보자.
12의 경우 이진수로 나타내면 1100 이다.
여기서 밑(제일 오른쪽)부터 쭉 올라가면서 가장 먼저(즉, 가장 오른쪽에서) 나타나는 1의 위치는 1<1>00 이다. 이를 LNZB(lowest nonzero bit)라고 부른다.
이걸 0으로 만들고, 숫자 전체에 1을 더하면 1001이다.
그러므로 12번 데이터는 1001(=9)부터 12까지를 '담당'한다.

이러한 구간을 어떻게 쉽게 알 수 있을까?
N 이
(...) 1 00...00 이라고 할 때,
(...) 0 00...01 을 구하는 방법은,
먼저 (N-1)을 하면
(...) 0 11...11 이 되고, 뒤의 1들을 제거하기 위해 N 과 (N-1)을 AND 연산한 후 1을 더하면 된다.
즉 \( (N \& (N-1)) + 1 \)을 담당한다.

트리 배열을 a[i]라고 하고,
예시로 1번부터 7번까지의 숫자들의 합을 구해보자.
먼저, a[7]은 이진수로 111이므로, (110+1 = 111)부터 111까지를 담당한다.
그럼 1부터 6까지의 합에 a[7]를 더하면 된다.
그럼 6은 110이므로 (100+1=101)부터 110까지, 즉 5부터 6까지를 담당한다.
그럼 1부터 4까지의 합에 a[6], a[7]를 더하면 된다.
4는 100이므로 0+1=1부터 100까지를 담당한다.
그러므로, 1부터 x까지의 합을 구하려면,
a[x]를 더해가면서, x가 들고 있는 구간의 왼쪽 bound 바로 밑까지의 값을 재귀적으로 더하면 된다.
왼쪽 bound는 위에서 알 수 있듯이 x&(x-1)이다.

함수로 나타내자면

int read(int x)
{
    int sum=0;
    while(x!=0) sum+=a[x], x=x&(x-1);
    return sum;
}

어떤 구간(l부터 r까지)의 숫자들의 합을 구하고 싶다면 read(r)-read(l-1) 하면 된다.

그러면, 처음에 a[x]를 채우는 방법이 필요하다.
일단, 구간끼리 걸치는 경우는 없다. 증명은 쉽게 가능하다.
따라서 x~x위치를 업데이트하고 나면,
자신을 포함하는 가장 작은 구간을 업데이트하고,
그것을 포함하는 가장 작은 구간을 업데이트하고, ... 하면 된다.
나를 포함하는 구간은 어떤걸까?

내 index를 x라고 하고, y=x&(x-1) 이라고 하면,
z에 대해, x<z이고 z&(z-1) <= y&(y-1)이어야 한다.
z와 x의 이진 자릿수가 같다고 생각해보면,
z는 x보다 큰데, LNZB를 지우고 나면 x보다 작아진다?
생각해보면 z의 LNZB가 x의 LNZB보다 더 왼쪽에 있어야(더 큰 수여야) 한다.
그런 z중 가장 작은 것은, x의 LNZB 자리에 1을 더하면 만들어진다.
그런 z가 없으려면(?), x는 이진수로 1111..1111 일테고, 이경우 정확히 1을 더한 수가 z가 된다.

결국 x에 x의 LNZB를 더하면 된다는 규칙이 나온다.

void update(int pos,int diff) {
    while(pos<=limit) a[pos]+=diff, pos+=(pos&-pos);
}

시간복잡도는 쿼리, 업데이트 모두 O(lgN)이다.

또한 정확히 N만큼의 공간을 사용한다.