백준 10868 : 최솟값 (C++) [Segment tree]

  세그먼트 트리를 연습할 수 있는 좋은 기본 예제이다.

 

**문제풀이 방법

- 새로운 값이 들어와서 트리가 바뀌는 업데이트가 없으므로, 트리 생성과 최소값을 구하는 함수만 작성

 

***코드

#include <stdio.h>
#include <vector>
#include <math.h>
#include <algorithm>

#define INF 2e9
#define MAX_N 100001

using namespace std;

int N, M;
vector<int> arr;
vector<int> segment_tree;
int min_value;

int build_segment_tree(int node, int start, int end) {
	if (start == end) {
		segment_tree[node] = arr[start];
		return segment_tree[node];
	}

	int left_child_node = node * 2;
	int right_child_node = node * 2 + 1;
	int mid = (start + end) / 2;

	int left_result = build_segment_tree(left_child_node, start, mid);
	int right_result = build_segment_tree(right_child_node, mid+1, end);

	segment_tree[node] = min(left_result, right_result);

	return segment_tree[node];

}

int Query(int node, int start, int end, int left, int right) {
	if (right < start || left > end) return INF;	// query의 범위가 노드가 포괄하는 범위 밖일 경우
	if (left <= start && end <= right) return segment_tree[node];		// query의 범위가 노드가 포괄하는 범위보다 클 경우 해당 노드 값 반환

	int left_child_node = node * 2;
	int right_child_node = node * 2 + 1;
	int mid = (start + end) / 2;
	
	int left_result = Query(left_child_node, start, mid, left, right);
	int right_result = Query(right_child_node, mid + 1, end, left, right);
	return min(left_result, right_result);
}


int main() {	

	scanf("%d %d", &N, &M);

	arr.clear();
	segment_tree.clear();

	// arr 배열 생성
	for (int i = 0; i < N; i++) {
		int value;
		scanf("%d", &value);
		arr.emplace_back(value);
	}

	// segment tree 생성
	int tree_Height = ceil(log2(N));
	int tree_Size = (1 << (tree_Height + 1));
	segment_tree.resize(tree_Size);
	build_segment_tree(1, 0, N - 1);

	// Query 수행
	for (int i = 0; i < M; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		a--;	// index가 0부터 시작하므로 1 빼주기
		b--;	// index가 0부터 시작하므로 1 빼주기

		min_value = Query(1, 0, N - 1, a, b);

		printf("%d\n", min_value);
	}

	return 0;
}

 

****주의할 점

- 최대값 반환할때 자료형 주의

 

 

<Reference>

- https://www.acmicpc.net/problem/10868

- https://yabmoons.tistory.com/439