Segment Tree(최댓값, 최소값 구하기)

백준 : 2357

주어진 구간의 최소값과 최댓값을 구하는 문제

 

public class MinMax {
    static int N, M;
    static long[] ar;
    static long[] minTree;
    static long[] maxTree;
    static long mini;
    static long maxi;

    static void build(int node, int start, int end) {
        // System.err.println(node + start + end);
        if (start == end) {
            minTree[node] = ar[start];
            maxTree[node] = ar[start];
        } else {

            int mid = (start + end) / 2;
            build(node * 2, start, mid);
            build(node * 2 + 1, mid + 1, end);
            minTree[node] = Math.min(minTree[node * 2], minTree[node * 2 + 1]);
            maxTree[node] = Math.max(maxTree[node * 2], maxTree[node * 2 + 1]);
        }
    }

    static void query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            return;
        }
        if (l <= start && end <= r) {
            mini = Math.min(minTree[node], mini);
            maxi = Math.max(maxTree[node], maxi);
            return;
        }
        int mid = (start + end) / 2;
        query(node * 2, start, mid, l, r);
        query(node * 2 + 1, mid + 1, end, l, r);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter((new OutputStreamWriter(System.out)));

        String[] firstLine = br.readLine().split(" ");
        N = Integer.parseInt(firstLine[0]);
        M = Integer.parseInt(firstLine[1]);

        ar = new long[N];

        for (int i = 0; i < N; i++) {
            ar[i] = Long.parseLong(br.readLine());
        }

        int h = Integer.highestOneBit(N);
        if (h < N) {
            h <<= 1;
        }

        int size = h * 4;
        minTree = new long[size];
        maxTree = new long[size];

        build(1, 0, N - 1);

        for (int i = 0; i < M; i++) {
            maxi = Long.MIN_VALUE;
            mini = Long.MAX_VALUE;
            String[] queryLine = br.readLine().split(" ");
            int start = Integer.parseInt(queryLine[0]);
            int end = Integer.parseInt(queryLine[1]);

            query(1, 0, N - 1, start - 1, end - 1);
            bw.write(mini + " " + maxi + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}