[자료구조] 2D 펜윅트리(2차원 펜윅트리)

2차원 펜윅트리를 구현하기 전에 1차원펜윅트리를 먼저 이해합니다.(https://wondangcom.tistory.com/1582)

1차원 배열이 여러개 인 행렬 구조의 데이터가 업데이트가 많은 경우 사용하게 되는데 1차원펜윅트리를 여러 개 이어 붙인 것이 2차원 펜윅트리라고 생각할 수 있다.

2차원의 구간합을 구하기 위해서 2개의 인덱스(y,x)가 필요하다.

그림으로 이해하면 다음과 같다.

(x1,y1) ~ (x2,y2) 의 구간합을 구하는 방법을 살펴 보면

먼저 (0,0)~(x2,y2) 의 구간합을 구한다.

이때 녹색과 하늘색 부분인 (0,0) ~ (x1,y2), (0,0)~(x2,y1) 구역을 빼 주면 되는 것을 확인 할 수 있다.

이렇게 두개의 구간 합을 빼 주면 (0,0) ~ (x1,y1) 구간의 합이 두번 빠지는 것을 확인할 수 있다.

따라서 sum(x1,y1,x2,y2) = sum(0,0,x2,y2) - sum(0,0,x1,y2) - sum(0,0,x2,y1) + sum(0,0,x1,y1) 이 되는 것을 확인 할 수 있다.

이것을 펜윅트리로 구현하면 다음과 같이 구현 할 수 있다.

(y,x) 위치에 현재값과의 차이를 더하는 경우 (y,x) ~ (n,n) 까지 모두 업데이트 해 주면 된다.

이때 y~n 까지 진행 역시 1차원 펜윅트리를 사용하여 이동하면 되고 x~n 까지 진행 역시 1차원 펜윅트리를 사용하면 되므로 코드는 다음과 같이 구현이 가능하다.

void update(int y, int x, int diff){
	for(int i = y; i <= N; i += (i & -i)) ///행을 이동하면서 
		for(int j = x; j <= N; j += (j & -j)) /// 해당 열의 뒷쪽을 모두 그 차이만큼 더하자 
			BIT[i][j] += diff;
}

(0,0) ~ (y,x) 까지의 구간합을 구하는 함수를 살펴 보면 1차원 펜윅트리를 이용하여 다음과 같이 구할 수 있다.

long long sum(int y, int x){
	long long res = 0;
	for(int i = y; i > 0; i -= (i & -i))
		for(int j = x; j > 0; j -= (j & -j))
			res += BIT[i][j];
	return res;
}

(y1,x1) ~ (y2,x2) 범위의 합을 구해 오는 함수를 살펴 보면 다음과 같이 구현이 가능하다.

long long query(int y1, int x1, int y2, int x2){
	return sum(y2, x2) - sum(y2, x1 - 1) - sum(y1 - 1, x2) + sum(y1 - 1, x1 - 1);
}

 

문제풀이

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=827&sca=6010 

JUNGOL

#include <bits/stdc++.h>
#define MAX 1024 + 10
using namespace std;
long long N, M, tree[MAX][MAX];
 
void update(int y, int x, int diff){
    for(int i = y; i <= N; i += (i & -i)) ///행을 이동하면서
        for(int j = x; j <= N; j += (j & -j)) /// 해당 열의 뒷쪽을 모두 그 차이만큼 더하자
            tree[i][j] += diff;
}
 
long long sum(int y, int x){
    long long res=0;
    for(int i=y; i>=1; i-=i&-i) {
        for(int j=x; j>=1; j-=j&-j) {
            res+=tree[i][j];
        }
    }
    return res;
}
 
long long query(int y1, int x1, int y2, int x2){
    return sum(y2, x2) - sum(y2, x1 - 1) - sum(y1 - 1, x2) + sum(y1 - 1, x1 - 1);
}
 
int main(){
    //freopen("input.txt","r",stdin);
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
 
 
    while(1){
        int cmd, x1, y1, x2, y2,val;
        cin >> cmd;
 
        if(cmd == 0){
            cin >> N;
        }
        else if(cmd==1)
        {
            cin >> y1 >> x1 >> val;
            update(y1+1, x1+1, val);
        }
        else if(cmd==2){
            cin  >> y1 >> x1 >> y2 >> x2;
            cout << query(y1+1, x1+1, y2+1, x2+1) << "\n";
        }
        else return 0;
    }
    return 0;
}