백준 2357 : 최솟값과 최댓값 (C++) [Segment tree]

 

  최솟값만 구하던 문제와 같은 방식으로 풀면 된다. 다만 두 개의 값을 반환하기 위해 segment tree를 각각 만들어서 진행한다.

 

**문제풀이 방법

- 최솟값을 구하기 위한 segment tree와 최댓값을 구하기 위한 segment tree를 각각 만들고, 연산하는 것도 각각 연산

 

***코드

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

#define INF 2e9
#define MAX_N 100001

using namespace std;

int N, M;
int min_value, max_value;
vector<int>arr;
vector<int>segment_tree_min;
vector<int>segment_tree_max;

int build_segment_tree_min(int node, int start, int end) {

	if (start == end) {
		segment_tree_min[node] = arr[start];
		return segment_tree_min[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_min(left_child_node, start, mid);
	int right_result = build_segment_tree_min(right_child_node, mid+1, end);
	segment_tree_min[node] = min(left_result, right_result);

	return segment_tree_min[node];
}


int build_segment_tree_max(int node, int start, int end) {

	if (start == end) {
		segment_tree_max[node] = arr[start];
		return segment_tree_max[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_max(left_child_node, start, mid);
	int right_result = build_segment_tree_max(right_child_node, mid + 1, end);
	segment_tree_max[node] = max(left_result, right_result);

	return segment_tree_max[node];
}

int Query_min(int node, int start, int end, int left, int right) {

	if (left > end || right < start) {
		return INF;
	}
	if (left <= start && end <= right) {	// query구간이 노드 포함 구간 보다 클 경우 노드값 반환
		return segment_tree_min[node];
	}

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

	int left_result = Query_min(left_child_node, start, mid, left, right);
	int right_result = Query_min(right_child_node, mid + 1, end, left, right);
	int min_value = min(left_result, right_result);

	return min_value;
}

int Query_max(int node, int start, int end, int left, int right) {

	if (left > end || right < start) {
		return 0;
	}
	if (left <= start && end <= right) {	// query구간이 노드 포함 구간 보다 클 경우 노드값 반환
		return segment_tree_max[node];
	}

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

	int left_result = Query_max(left_child_node, start, mid, left, right);
	int right_result = Query_max(right_child_node, mid + 1, end, left, right);
	int max_value = max(left_result, right_result);

	return max_value;
}

int main() {
	//freopen("input.txt", "r", stdin);

	// 초기화
	scanf("%d %d", &N, &M);

	arr.clear();
	segment_tree_min.clear();
	segment_tree_max.clear();
	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_min.resize(tree_Size);
	segment_tree_max.resize(tree_Size);

	build_segment_tree_min(1, 0, N - 1);
	build_segment_tree_max(1, 0, N - 1);

	// Query 수행
	for (int i = 0; i < M; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		a--;
		b--;

		min_value = Query_min(1, 0, N - 1, a, b);
		max_value = Query_max(1, 0, N - 1, a, b);

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

	return 0;
}

 

****주의할 점

- 쿼리 수행시 구간이 노드 범위 밖일 경우 최댓값과 최솟값 각 경우의 반환값 주의 (0, INF)

 

 

<Reference>

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

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