boj 2357: 최솟값과 최댓값

세그먼트 트리는 구간의 최솟값을 구하는데 가장 효율적인 자료구조이다.

 

세그먼트 트리

 

• 각 노드에 저장되는 값은 3가지이다 --> 저장되는 칸의 번호, 구간 시작, 구간 끝 (구간시작==구간끝: 리프 노드)
• 예를 들어 3~5 노드는 구간 3~5에서 최솟값을  저장하고 있다.
• 배열을 이용해서 구할 수 있다. --> x의 왼쪽 자식은 2x, 오른쪽 자식은 2x+1 이런 식으로,,,
• 모든 노드는 자식이 무조건 0개 또는 2개이다.
• 리프 노드가 n개인 full binary tree가 필요한 노드의 개수: 높이 h=lgn일 때 2^(h+1)

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();

		int arr[] = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			arr[i] = in.nextInt();
		}

		int h = (int) Math.ceil(Math.log(n) / Math.log(2));
		int maxTree[] = new int[1 << (h + 1)];
		int minTree[] = new int[1 << (h + 1)];

		initTree(true, arr, maxTree, 1, 1, n);
		initTree(false, arr, minTree, 1, 1, n);

		for (int i = 0; i < m; i++) {
			int start = in.nextInt();
			int end = in.nextInt();

			System.out.print(findSegment(false, minTree, 1, 1, n, start, end) + " ");
			System.out.println(findSegment(true, maxTree, 1, 1, n, start, end));
		}
	}

	public static int initTree(boolean isMaxTree, int[] arr, int[] tree, int index, int start, int end) {
		if (start == end) {
			tree[index] = arr[start];
			return tree[index];
		}

		int mid = (start + end) / 2;

		if (isMaxTree) {
			tree[index] = Math.max(initTree(isMaxTree, arr, tree, index * 2, start, mid),
					initTree(isMaxTree, arr, tree, index * 2 + 1, mid + 1, end));

			return tree[index];
		} else {
			tree[index] = Math.min(initTree(isMaxTree, arr, tree, index * 2, start, mid),
					initTree(isMaxTree, arr, tree, index * 2 + 1, mid + 1, end));

			return tree[index];
		}
	}

	public static int findSegment(boolean isFindMax, int[] tree, int index, int start, int end, int left, int right) {

		if (left > end || right < start) {
			// 범위와 관계 없어서 볼 필요가 없을 때
			return -1;
		}

		if (left <= start && right >= end) {
			// 범위에 구간이 포함되는 경우, left - start - end - right
			return tree[index];
		}

		// 범위에 구간이 일부 포함되는 경우
		// left - start - right - end 또는
		// start - left - right - end
		int mid = (start + end) / 2;
		if (isFindMax) {
			return Math.max(findSegment(isFindMax, tree, index * 2, start, mid, left, right),
					findSegment(isFindMax, tree, index * 2 + 1, mid + 1, end, left, right));
		} else {
			int segmentLeft = findSegment(isFindMax, tree, index * 2, start, mid, left, right);
			int segmentRight = findSegment(isFindMax, tree, index * 2 + 1, mid + 1, end, left, right);

			if (segmentLeft == -1) {
				return segmentRight;
			} else if (segmentRight == -1) {
				return segmentLeft;
			} else {
				return Math.min(segmentLeft, segmentRight);
			}
		}
	}
}