c언어 14438번 수열과 쿼리 17 (백준)

#include <stdio.h>
#define M 1000000001

int a[100001]; //요소를 담을 배열
int tree[400004]; //tree를 구성할 배열

int min(int x, int y) { //최솟값 구하기
	return (x<y) ? x : y;
}

int init(int s, int e, int node) { //트리 초기화
	if(s==e) return tree[node] = a[s];
	int mid = (s+e)/2;
	return tree[node] = min(init(s, mid, node*2), init(mid+1, e, node*2+1));
} 

int find(int s, int e, int node, int l, int r) { //범위내의 최솟값 찾기
	if(s > r || e < l) return M;
	if(l<=s && e<=r) return tree[node];
	int mid = (s+e)/2;
	return min(find(s, mid, node*2, l, r), find(mid+1, e, node*2+1, l, r));
}

void update(int s, int e, int node, int index) { //트리 갱신하기
	if(s > index || index > e) return;
	if(s==e) {
		if(s==index) tree[node] = a[index];
		return;
	}
	 
	int mid = (s+e)/2;
	update(s, mid, node*2, index);
	update(mid+1, e, node*2+1, index);
	tree[node] = min(tree[node*2], tree[node*2+1]);
	return;
}

int main(void) {
	int n, m;
	scanf("%d", &n);
	for(int i=1; i<=n; i++) scanf("%d", &a[i]); //요소들을 입력받습니다.
	
	init(1, n, 1);
	
	scanf("%d", &m);
	while(m--) {
		int b, c, d;
		scanf("%d %d %d", &b, &c, &d);
		if(b==1) {
			a[c] = d;
			update(1, n, 1, c); //갱신합니다
		} else {
			printf("%d\n", find(1, n, 1, c, d)); //최솟값을 찾습니다.
		}
	}
}

주의 : 이것은 왕초보가 짠 코드 입니다. (백준에 엄청난 분들의 코드를 보시는 것을 추천합니다)

 

풀이 : segment tree

 

1. segment tree을 위한 함수들을 만듭니다.

 init : 트리를 초기화 합니다.

 update : 요소가 바뀔 때 마다 관련된 tree의 노드들을 갱신합니다.

 find : 주어진 범위내의 최솟값을 찾습니다.

 

2. 덤으로 최솟값을 구할 함수도 만듭니다.(min)

 

3. 요소들을 담을 배열과, 트리들을 구성할 배열을 전역으로 만듭니다. (정적 메모리 할당)

 

4. n입력 -> 요소들을 입력

5. 트리를 초기화합니다.

6. m입력

7. 1을 입력받으면  update //갱신

8. 2을 입력받으면 범위내에서 가장 작은 값을 출력

 

 

https://www.acmicpc.net/problem/14438

14438번: 수열과 쿼리 17