세그먼트트리

1. RMQ

• 구간에서 최소값 구하기
• 배열 A[1], A[2], … , A[N]가 있고, 이중 A[i], … ,A[j] 중에서 최소 값을 찾아 출력
• 이러한 연산이 총 Q개 주어짐
• 1개 : $O(N)$ , Q개 : $O(NQ) N,Q <= 10만$## 1. RMQ

2. 세그먼트 트리

• 자식 2개 또는 없음.
  
• 노드는 start ~ end 까지 최소 값을 가지고 있음
• start ~ mid 와 mid+1-end 두 개의 최소 값 중에 최소 값이 start ~ end의 최소 값.
• 트리의 사이즈 계산 : N = 2^h -> logN=log2^h -> logN = hlog2 -> longN/log2 =h
  
• N = 5 일 경우 3 ~ 4 조회

  int h = (int)Math.ceil(Math.log(5) / Math.log(2));
  int tree_size = (1 << (h+1));

• 최초 트리 정렬

public static void init(long[] tree, long[] arr, int node, int start, int end) {
        if(start == end){
            tree[node] = arr[start];
            return;
        }
        int mid = (start + end) / 2;
        int leftNodeIdx = 2 * node;
        int rightNodeIdx = (2 * node) + 1;
        if(start != end){
            init(tree, arr, leftNodeIdx, start, mid);
            init(tree, arr, rightNodeIdx, mid + 1, end);
            tree[node] = Math.min(tree[leftNodeIdx], tree[rightNodeIdx]);
        }
    }