[Java] Segment Tree 구현

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

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);




    }
}

class SegmentTree{
    int N; //size
    int [] tree;

    int merge(int left, int right){
        return left+right; // sum
    }

    int buildRec(int [] arr, int node, int nodeLeft, int nodeRight){
        if(nodeLeft == nodeRight)
            return tree[node] = arr[nodeLeft];

        int mid = nodeLeft + (nodeRight-nodeLeft)/2;
        int leftVal = buildRec(arr, node*2, nodeLeft, mid);
        int rightVal = buildRec(arr, node*2+1,mid+1, nodeRight);

        return tree[node] = merge(leftVal, rightVal);
    }

    void build(int [] arr, int size){
        N = size;
        tree = new int[N*4];

        buildRec(arr,1,0,N-1);
    }

    int queryRec(int left, int right, int node, int nodeLeft, int nodeRight){
        if(right < nodeLeft || left > nodeRight)
            return 0;
        if(left <= nodeLeft && nodeRight <= right)
            return tree[node];

        int mid = nodeLeft + (nodeRight-nodeLeft)/2;
        return merge(queryRec(left,right,node*2,nodeLeft,mid),
                queryRec(left,right,node*2+1,mid+1,nodeRight));
    }

    int query(int left, int right){
        return queryRec(left,right,1,0,N-1);
    }

    int updateRec(int index, int newValue, int node, int nodeLeft, int nodeRight){
        if(index < nodeLeft || index > nodeRight)
            return tree[node];
        if(nodeLeft == nodeRight)
            return tree[node] = newValue;

        int mid = nodeLeft + (nodeRight-nodeLeft)/2;
        int leftVal = updateRec(index, newValue,node*2, nodeLeft, mid);
        int rightVal = updateRec(index, newValue,node*2+1,mid+1, nodeRight);
        return tree[node] = merge(leftVal,rightVal);
    }

    int update(int index, int newValue){
        return updateRec(index, newValue, 1, 0 ,N-1);
    }

}

 

 

https://www.youtube.com/watch?v=ahFB9eCnI6c&ab_channel=%EA%B0%9C%EB%B0%9C%EC%9E%90%EC%98%81%EB%A7%A8