[백준 BoJ] 1357 - 최솟값과 최댓값

// https://www.acmicpc.net/problem/2357
// 최솟값과 최댓값

#include<iostream>
#include<algorithm>
using namespace std;

int INF = 1000000001;
int N, M;
int arr[100002];
int max_tree[4 * 100002 + 4];
int min_tree[4 * 100002 + 4];

int init_min(int start, int end, int node) {
	if (start == end) return min_tree[node] = arr[start];

	int mid = (start + end) / 2;

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

}

int init_max(int start, int end, int node) {
	if (start == end) return max_tree[node] = arr[start];

	int mid = (start + end) / 2;

	return max_tree[node] = max(init_max(start, mid, node * 2), init_max(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 min_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 get_max(int start, int end, int node, int left, int right) {
	if (left > end || right < start) return 0;

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

	int mid = (start + end) / 2;

	return max(get_max(start, mid, node * 2, left, right), get_max(mid + 1, end, node * 2 + 1, left, right));
}

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

	cin >> N >> M;

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

	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		cout << get_min(1, N, 1, a, b) << " ";
		cout << get_max(1, N, 1, a, b) << "\n";
	}
}

• 세그먼트 트리