펜윅트리 - BOJ) 11658 구간합 구하기 3

11658 구간합 구하기 3을 풀려고 2d segment tree로 풀다가 시간초과나서 빡쳤다.

아마 initialization에서 시간초과가 뜨는 것 같은데 화가 난다. 좀 쉽게 코딩하려다가 봉변 당한것 같다.

각설하고 예전부터 펜윅 트리에 대해 본 적이 있는데 사실 그 날 공부하면 그 다음날 까먹는 그런 형태의 트리이다.

좋은 설명은 여기에 있다.

위를 읽고 나름대로 정리를 해보면

${2^0, 2^1, 2^2, 2^3, ...}$와 같은 2의 제곱수를 생각해보자.

$tree[index]$에 대해 만약 $index$가 $k = argmax_{n} 2^n$로 나누어진다고 생각하면 해당 $tree[index]$ 는 k개의 원소를 갖는다. 심지어 $arr[index]$를 포함한 원소말이다.

즉 $arr[index-k+1], arr[index-k+2], ... ,arr[index]$의 원소의 sum을 $tree[index]$가 표현하고 잇는 것이다.

재밌는 것은 index를 이진수로 나타낼 때 11010와 같이 나타낼 수 있는데, 이 때 1이 나타나는 가장 끝의 위치를 이용하여 쉽게 sum과 update를 구할 수 있다.

index & -index 가 1이 나타나는 가장 끝의 위치를 말한다.

아래는 update와 sum에 대한 코드이다.

void update(int x, int y, int diff) {

    while(y <= N) {

        tree[x][y] += diff;

        y += (y & -y);

}

}

int sum(int x, int y) {

    int ans = 0;

    while(y >= 1) {

        ans += tree[x][y];

        y -= (y & -y);

}

    return ans;

}

Giyeon with CS