728x90
반응형
동작방식
참고사이트 설명 참조
시간복잡도
세그먼트 트리를 이용할 경우 기존의 for문이 O(N)의 시간 복잡도보다 빠른 O(logN)의 시간 복잡도
참고사이트
https://cocoon1787.tistory.com/313
[자료구조] 세그먼트 트리(구간트리, Segment Tree)로 구간 내 최소값 찾기
세그먼트 트리(Segment Tree)란? 알고리즘 문제를 풀다 보면 정렬되어 있지 않은 구간 내의 합이나 최솟값들을 빠르게 찾아야 하는 경우가 많습니다. 질문이 1개일 경우 간단하게 for문을 통해서 O(N)
cocoon1787.tistory.com
기본코드
| 10 4 75 30 100 38 50 51 52 20 81 5 1 10 3 5 6 9 8 10 |
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();
}
}728x90
반응형
