Typiler

동작방식

참고사이트 설명 참조

시간복잡도

 세그먼트 트리를 이용할 경우 기존의 for문이 O(N)의 시간 복잡도보다 빠른 O(logN)의 시간 복잡도

참고사이트

https://cocoon1787.tistory.com/313

기본코드

package segmenttree;

import java.io.*;
import java.util.StringTokenizer;

public class Rmq {

    static int[] numbers;
    static int[][] questions;
    static int[] tree;

    public static void init(int node, int start, int end) {
        if (start == end) {
            tree[node] = numbers[start];
        } else {
            init(node*2, start, (start+end)/2);
            init(node*2+1, (start+end)/2+1, end);
            tree[node] = Math.min(tree[node*2],tree[node*2+1]);
        }
    }

    public static int query(int node, int start, int end, int a, int b) {
        if (a > end || b < start) {
            return -1;
        }
        if (a <= start && end <= b) {
            return tree[node];
        }
        int left = query(node*2, start, (start+end)/2, a, b);
        int right = query(node*2+1, (start+end)/2+1, end, a, b);
        if (left == -1) {
            return right;
        } else if (right == -1){
            return left;
        } else {
            return Math.min(left, right);
        }
    }

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("input\\rmq.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        numbers = new int[N];
        questions = new int[M][2];
        tree = new int[N*4];

        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            questions[i][0] = Integer.parseInt(st.nextToken());
            questions[i][1] = Integer.parseInt(st.nextToken());
        }

        br.close();

        init(1, 0, N-1);

//        for (int i=0; i<tree.length; i++) {
//            System.out.println("tree[" + i + "] : " + tree[i]);
//        }

        for (int i=0; i<M; i++) {
            bw.write(query(1, 0, N-1, questions[i][0]-1, questions[i][1]-1)+"\n");
        }

        bw.flush();
        bw.close();
    }
}