[BOJ] 10868 : 최솟값 - travelbeeee

문제 : https://www.acmicpc.net/problem/10868

---

세그트리

자료구조 세그트리를 이용하는 전형적인 문제로, 구간의 최솟값을 가질 수 있게 세그트리를 만들어주면 됩니다.

#include<iostream>
#include<algorithm>

using namespace std;

int N[100000] = {};
int tree[400000] = {};

int init(int index, int start, int end) {
	int mid = (start + end) / 2;

	if (start == end)
		return tree[index] = N[start];
	else
		return tree[index] = min(init(2 * index + 1, start, mid), init(2 * index + 2, mid + 1, end));
}

// 제일 작은 값을 찾자.
int get_min(int index, int start, int end, int left, int right) {
	int mid = (start + end) / 2;

	if (end < left || right < start){
		return 1987654321;
	}
	if (left <= start && end <= right){
		return tree[index];
	}

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


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

	int n, m, a, b;
	long long ans = 0;
	
	cin >> n >> m;

	for (int i = 0; i < n; i++)
		cin >> N[i];

	init(0, 0, n - 1);

	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		cout << get_min(0, 0, n - 1, a - 1, b - 1) << '\n';
	}

}

---