BOJ 10868 최소값

사용한 알고리즘

세그먼트 트리

알고리즘 설명

기초적인 세그먼트 트리이다.
이분트리 형태로 구간의 최솟값을 저장한다.
이후에 각 쿼리들에 대한 최솟값을 출력한다.

참고

라이님의 블로그 포스팅을 참고하였다.

풀이

// baekjoon 10868 yechan
#include <cstdio>
#include <algorithm>
using namespace std;
const int SIZE=1<<17;

int N, M, x, a, b;
int arr[SIZE*2];

void update(int i, int val) {
	i += SIZE;
	arr[i] = val;
	while (i > 1) {
		i /= 2;
		arr[i] = min(arr[i*2], arr[i*2+1]);
	}
}

int segMin(int nodeL, int nodeR, int nodeNum, int L, int R) {
	if (R < nodeL || nodeR < L) return 1e9;
	if (L <= nodeL && nodeR <= R) return arr[nodeNum];
	int mid = (nodeL + nodeR) / 2;
	return min(segMin(nodeL, mid, nodeNum*2, L, R), segMin(mid+1, nodeR, nodeNum*2+1, L, R));
}

int segMin(int L, int R) {
	return segMin(0, SIZE-1, 1, L, R);
}

int main() {
	fill(arr, arr+SIZE*2, 1e9);
	scanf("%d%d", &N, &M);
	for (int i=1; i<=N; i++) {
		scanf("%d", &x);
		update(i, x);
	}
	while (M--) {
		scanf("%d%d", &a, &b);
		printf("%d\n", segMin(a,b));
	}
	return 0;
}