c언어 11658번 구간 합 구하기 3 (백준)

#include <stdio.h>
#define N 1025
int arr[N][N] = {};
int tree[N][N*4] = {};
int tree2[N*4][N*4] = {};
int dif[N*4] = {};

int find2(int start, int end, int node, int left, int right, int treeNode) {
	if(start > right || end < left) return 0;
	if(left <= start && end <= right) return tree2[treeNode][node];
	int m = (start+end)/2;
	return find2(start, m, node*2, left, right, treeNode) + find2(m+1, end, node*2+1, left,right, treeNode);
}

int find1(int start, int end, int node, int left, int right, int y1, int y2, int n) {
	if(start > right || end < left) return 0;
	if(left <= start && end <= right) {
		return find2(1,n,1,y1,y2,node);
	}
	int m = (start+end)/2;
	return find1(start, m, node*2, left, right, y1, y2,n) + find1(m+1, end, node*2+1, left, right, y1, y2,n);
}

void update1(int start, int end, int node, int index, int dif, int treeNode) {
	if(start > index || end < index) return;
	tree[treeNode][node] += dif;
	if(start==end) return;
	int mid = (start+end)/2;
	update1(start,mid,node*2,index,dif,treeNode);
	update1(mid+1,end,node*2+1,index,dif,treeNode);
}

void update2(int start, int end, int node, int index, int nodeCnt) {
	if(start > index || end < index) return;
	for(int i=1; i<=nodeCnt; i++) tree2[node][i] += dif[i];
	if(start==end) return;
	int mid = (start+end)/2;
	update2(start,mid,node*2,index,nodeCnt);
	update2(mid+1,end,node*2+1,index,nodeCnt);
}

int main(void) {
	int n, m, nodeCnt;
	scanf("%d %d",&n,&m);
	nodeCnt = n*2-1;
	
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			scanf("%d",&arr[i][j]);
			update1(1,n,1,j,arr[i][j],i);
		}
		for(int j=1; j<=nodeCnt; j++) dif[j] = tree[i][j];
		update2(1, n, 1, i, nodeCnt);
	}	
	
	while(m--) {
		int w,x1,y1,x2,y2;
		scanf("%d",&w);
		if(w==0) {
			scanf("%d %d %d",&x1,&y1,&x2);
			for(int i=1;i<=nodeCnt; i++) dif[i] = tree[x1][i];
			
			update1(1,n,1,y1,x2-arr[x1][y1],x1);
			arr[x1][y1] = x2;
			
			for(int i=1;i<=nodeCnt; i++) dif[i] = tree[x1][i]-dif[i];
			update2(1,n,1,x1,nodeCnt);
		}
		else if(w==1) {
			scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
			printf("%d\n",find1(1,n,1,x1,x2,y1,y2,n));
		}
	}
}

 

풀이 : 이차원 세그먼트 트리

 

이차원 세그먼트 트리는, 여러 세그먼트트리들을 말단노드로 취하는 세그먼트트리 입니다.

이를 구현하려면 많은 공간이 필요하기 때문에, 범위 수정 문제가 아니라면 펜윅트리로 만드는 것이 효율적입니다.

 

이차원 세그먼트 트리의 구현은

1. 일차원 세그먼트 트리들을 구현하기 (update1, find1)

2. 일차원 세그먼트 트리들을 말단노드로 삼는 새로운 세그먼트 트리 구현하기 (update2, find2)

 

일차원 세그먼트 트리에서 값 1개를 수정할 때는, 기존 값 - 수정할 값 을 관련있는 노드에 더해주기만 하면 되었지만

일차원 세그먼트 트리의 값이 수정되면 이를 취하는 이차원 세그먼트 트리의 값도 수정해주어야 합니다.

이 때는 수정 되기 전 세그먼트 트리의 모든 값 - 수정 한 이후 세그먼트 트리의 값들을 관련있는 이차원 세그먼트 트리의 노드마다 수정해주어야 합니다. (시간이 많이 걸리는 요인입니다)

 

값을 find(탐색) 할 때는

x(첫번째 차원), y(두번째 차원) 의 개념으로 바라보아야 합니다.

 

find1()은 x의 범위내의 모든 세그먼트트리들의 합의 노드들의 번호를 얻은다음

find2()에서 find1()에서 얻은 노드들의 번호를 가지고 거기서 y범위내의 값들을 가져오면 됩니다. (이건 기존의 세그먼트 트리와 동일합니다)

 

위의 방식보단 펜윅트리로 구현하는 것이 매우 효율적입니다.