Fenwick Tree(Binary Indexed Tree)

http://jason9319.tistory.com/282 문제를 lazy progatition을 이용한 segment tree를 이용하다가 멘탈이 나가서 fenwick tree를 공부하였다. (https://www.acmicpc.net/board/view/15993)

펜윅트리는 BIT(Binary Indexed Tree)로도 불리며 갱신이 이루어지는 range의 구간 합 연산을 빠르게 해결해주는 자료구조로 알려져있다.

자료구조의 정당성과 시간복잡도등은 https://www.acmicpc.net/blog/view/21에 잘 설명이 되어있고 여기서는 간단하게 사용법만 알아보겠다.

ll tree[MAX_N+1];
void update(ll x, ll val) {
    while (x <= MAX_N) {
        tree[x] += val;
        x += (x&-x);
    }
}
ll query(int x) {
    ll sum = 0;
    while (x > 0) {
        sum += tree[x];
        x -= (x&-x);
    }
    return sum;
}

세그먼트 트리에 비해 소스코드가 매우 간결하다

업데이트 연산 쿼리 연산 모두 log시간에 해결되며 update(x,val)은 x에 val만큼을 더해주는 연산이며

query(x)는 1~x까지의 구간합을 출력하게 된다.

따라서 x~y까지의 구간합을 구하고 싶을 때 query(y)-query(x-1)을 출력하면 된다.

위의 소스에서 update연산은 한 지점으로의 update 연산만을 가능케하는데

약간의 테크닉을 활용하여 query 함수에 대한 정의를 바꾼다면 구간에 대한 update연산도 log시간에 해결해줄 수 있다.

예를들어 1~N의 range에 x~y까지의 구간에 모두 val씩 업데이트한다고 생각해보자

그렇다면 update(x,val) ,update(y+1,-val)을 이용할 수 있다.

이렇게 업데이트를 할 경우 (int i: x~y) 에 대한 query(i)는 1~i까지의 합을 나타내기 때문에 업데이트 된 x를 가지게 되며 y+1 이상의 수는 x와 -x을 더하게 되어 상쇄되게 된다.

이렇게 구성할 경우 구간에 대한 합연산이 log시간에 처리되며 query(i)는 기존 1~i까지의 합을 나타내는것이 아닌 i위치의 누적합을 출력하게 된다.

void go(ll x, ll y, ll val) {
    if (x <= y)
        update(x, val), update(y + 1, -val);    //구간 x~y까지의 업데이트 
    else {
        update(1, val);            //구간 1~x, y~MAX_N까지의 업데이트
        update(x + 1, -val);
        update(y, val);
    }
}