[ 백준 10868 ] 최솟값 (C++, 세그먼트 트리)

[문제보기]

 

[해결과정]

 - 세그먼트 트리 활용

 

[소스코드]

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<math.h>
using namespace std;

typedef long long ll;
#define MAX 400005

int n, m, a, b;
ll minTree[MAX*10];
ll node[MAX];

// init(배열, 위치, 시작점, 끝점)
ll minInit(ll arr[], ll treeIdx, ll dataIdxL, ll dataIdxR) {
	if (dataIdxL == dataIdxR) return minTree[treeIdx] = arr[dataIdxL - 1];
	ll mid = (dataIdxL + dataIdxR) / 2;
	return minTree[treeIdx] = min(minInit(arr, 2 * treeIdx, dataIdxL, mid), minInit(arr, 2 * treeIdx + 1, mid + 1, dataIdxR));
}

// query(시작위치, 끝위치, 위치, 시작점, 끝점)
ll minQuery(ll queryL, ll queryR, ll treeIdx, ll dataIdxL, ll dataIdxR) {
	if (queryL > dataIdxR || dataIdxL > queryR) return 1000000001;
	if (dataIdxL >= queryL && queryR >= dataIdxR) return minTree[treeIdx];
	ll mid = (dataIdxL + dataIdxR) / 2;
	return min(minQuery(queryL, queryR, 2 * treeIdx, dataIdxL, mid), minQuery(queryL, queryR, 2 * treeIdx + 1, mid + 1, dataIdxR));
}


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	// input
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> node[i];

	// init
	minInit(node, 1, 1, n);

	// query
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		cout << minQuery(a, b, 1, 1, n) << "\n";
	}
	

	// debug
	/*
	for (int i = 0; i < n * 6; i++) cout << minTree[i] << " ";
	*/

	return 0;
}

 

[해결 과정 중 실수한 부분 / 잡담]

 -

 

[관련 문제 혹은 비슷한 문제]

 최솟값과 최댓값