세그먼트트리

1. RMQ

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

2. 세그먼트 트리

• 자식 2개 또는 없음.
  
• 노드는 start ~ end 까지 최소 값을 가지고 있음
• start ~ mid 와 mid+1-end 두 개의 최소 값 중에 최소 값이 start ~ end의 최소 값.
• 트리의 사이즈 계산 : $N = 2^h \rightarrow logN=log2^h \rightarrow logN = hlog2 \rightarrow \frac{logN}{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]);
        }
    }

• 호출

init(tree, arr, 1, 0, 4);

• 구간 최소값 조회

public static long query(long[] tree, int node, int start, int end, int left, int right) {
        if (end < start || left > end) {
            return -1;
        }
        if (left <= start && right >= end) {
            return tree[node];
        }
        int mid = (start + end) / 2;
        int leftNodeIdx = 2 * node;
        int rightNodeIdx = (2 * node) + 1;
        long leftNode = query(tree, leftNodeIdx, start, mid, left, right);
        long rightNode = query(tree, rightNodeIdx, mid + 1, end, left, right);
        if(leftNode == -1){
            return rightNode;
        }
        if(rightNode == -1){
            return leftNode;
        }
        return Math.min(leftNode, rightNode);
    }

• 호출

query(tree, 1, 0, 4, 3, 4)

• 업데이트 방식 1 (3번째 인덱스 값 변경)

public static void update(int[] tree, int node, int start, int end, int index, int value){
        if (start > index || end < index) {
            return;
        }
        if(start == end){
            tree[node] = value;
            return;
        }
        int mid = (start + end) / 2;
        int leftNodeIdx = node * 2;
        int rightNodeIdx = leftNodeIdx + 1;
        update(tree, leftNodeIdx, start, mid, index, value);
        update(tree, rightNodeIdx, mid + 1, end, index, value);
        tree[node] = tree[leftNodeIdx] + tree[rightNodeIdx];
    }

• 업데이트 방식 2 (3번째 인덱스 값의 차이(diff) 만큼 더해줌)

public static void update(int[] tree, int node, int start, int end, int index, int diff) {
        if (start > index || end < index) {
            return;
        }
        if(start == end){
            tree[node] += diff;
            return;
        }
        int mid = (start + end) / 2;
        int leftNodeIdx = node * 2;
        int rightNodeIdx = leftNodeIdx + 1;
        update(tree, leftNodeIdx, start, mid, index, value);
        update(tree, rightNodeIdx, mid + 1, end, index, value);
    }

• 호출

update(tree, 1, 1, 4, 3, value);
int diff = 값 - arr[3]; //상황에 따라 다르다. 원본에서 빼줘야 할때도 있음.
update(tree, 1, 1, 4, 3, diff);