c언어 11505번 구간 곱 구하기 (백준)

#include <stdio.h>
#define M 1000000007
long long tree[4000004] = {};

long long update(int s, int e, int node, int index, long long dif) {
	if(s>index || e<index) return tree[node]; //수정할 노드가 아니므로 수정하지 않고 리턴
	if(s==e) return tree[node] = dif;
	int m = (s+e)/2;
	return tree[node] = update(s,m,node*2,index,dif) * update(m+1,e,node*2+1,index,dif) % M;
}

long long find(int s, int e, int node, int l, int r) {
	if(s>r || e<l) return 1;
	if(l<=s && e<=r) return tree[node];
	int m = (s+e)/2;
	return find(s,m,node*2,l,r) * find(m+1,e,node*2+1,l,r) %M;	
}

int main(void) {
	int n,m,k;
	scanf("%d %d %d",&n,&m,&k);
	m+=k;
	
	for(int i=1; i<=n; i++) {
		long long tmp;
		scanf("%lld",&tmp);
		update(1,n,1,i,tmp);
	}
	while(m--) {
		long long a,b,c;
		scanf("%lld %lld %lld",&a,&b,&c);
		if(a==1) {
			update(1,n,1,b,c);	
		}
		else if(a==2) {
			printf("%lld\n",find(1,n,1,b,c));
		}
	}
}

 

 

풀이 : segment tree

 

핵심은 갱신을 할 때도, 값을 찾을 때도 항상 module 연산을 해주어야 합니다.

 

segment tree에서 update을 하는 방법은 2가지 방법이 존재합니다.

1. root에서 말단 노드 순으로 갱신하는 방법 (이 경우 함수는 값을 return 할 필요가 없습니다)

2. 말단노드에서 root 순으로 갱신하는 방법 (이 경우 함수는 값을 return 할 필요가 있습니다)

 

이 때 1번 방식대로 update을 하게 되면 문제가 발생합니다.

이 문제는 0 또한 입력값으로 주어질 수 있기 때문에 root부터 수정을 하게 되면 한 번 0이 된 노드는 계속 0으로 고정됩니다. 그러나 2번 방식대로 하면 0이 되더라도 새로운 0이 아닌 값으로 대체되면 다른 노드들도 전부 원하는대로 수정되게 됩니다.

 

root에서 말단노드 순으로 갱신

말단노드에서 root 순으로 갱신