セグメントツリー

1. RMQ

2.セグメントツリー

には2人または子供がいません.

木の寸法計算:N=2 h→logN=log 2 h→logN=hlog 2→logN=hN=2^h右矢印logN=log 2^h\右矢印logN=hlog 2\右矢印\frac{logn}=hN=2 h→logN=log 2 hlog 2→log 2 hlog 2→log 2 hlog 2

  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)

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];
    }

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);