[백준 BoJ] 10868 - 최솟값

100000개의 테스트 개수를 주고, 1부터 1,000,000,000까지의 범위를 주어졌을 때 일반적으로 코드를 짜면 시간초과가 발생한다. 세그먼트 트리를 이용해 문제를 해결하면 시간초과를 방지할 수 있음

// https://www.acmicpc.net/problem/10868
// 최솟값

#include<iostream>
#include<algorithm>

using namespace std;
int arr[100002];
int tree[4 * 100002 + 4];
int INF = 1000000001;
int init(int start, int end, int node) {
	if(start == end) return tree[node] = arr[start];

	int mid = (start + end) / 2;

	return tree[node] = min(init(start, mid, node * 2) , init(mid + 1, end, node * 2 + 1));

}

int get_min(int start, int end, int node, int left, int right) {
	if (left > end || right < start) return INF;

	if (left <= start && end <= right) return tree[node];

	int mid = (start + end) / 2;

	return min(get_min(start, mid, node * 2, left, right), get_min(mid + 1, end, node * 2 + 1, left, right));

}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N, M;
	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}

	init(1, N, 1);

	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;

		cout << get_min(1, N, 1, a, b) <<"\n";
	}
}

• 세그먼트 트리