<알고리즘> 4. 세그먼트트리 JAVA

가. 세그먼트 트리 

 a. 무엇인가

  -   어떤 배열의 구간합을 트리형태로 저장

 

 b. 특징

  -  배열로 구간합을 저장하고 (S[i]= S[i-1]+A[i]) 원하는 구간을 (S[R] - S[L-1])의 형태로 구현이 가능[O(1)] 

  -  하지만 배열의 값이 바뀌는 경우 바뀔때마다 구간합을 더해서 저장해야한다 O(N*변경)

  -  세그먼트 트리는 이를 O(logN)으로 만들어 줄 수 있다.

 

나. 구현

 a. DFS 및 이분탐색의 활용

  -  node는 1번부터 시작하며 node*2가 왼쪽 자식노드 node*2+1이 오른쪽자식 노드가 된다.

  -  트리의 구성은 이분탐색으로 쭉쭉 내려가면서 start랑 end가 같아질때 해당 노드번호에 요소를 저장한다.

  -  리프에 저장이 끝나면 위로 돌아와서 해당구간을 더한 값을 저장해준다.

public class 세그먼트트리 {

    public static void main(String[] args){

        new 세그먼트트리().start();
    }
    int[] arr;
    int[] tree;

    public void start(){
        arr = new int[]{1, 2, 3, 4, 5, 6};
        tree = new int[arr.length*3];

        트리만들기(1,0,arr.length-1);
        System.out.println(구간합찾기(1,0, arr.length-1, 1,3));
        int temp = arr[2];
        arr[2] = 2;
        int diff = temp - arr[2];
        변경된요소_업데이트(1,0,arr.length-1,2,diff);
        System.out.println(구간합찾기(1,0, arr.length-1, 1,3));

    }

    public int 트리만들기(int node,int start,int end){
        if(start == end){
            return tree[node] = arr[start];
        }else {
            // 왼쪽 단말과 오르쪽 단말을 더한다 (구간합)
            int mid = (start+end)/2;
            return tree[node] = 트리만들기(node*2,start,(start+end)/2)
                + 트리만들기(node*2+1,(start+end)/2+1,end);
        }
    }

    public int 구간합찾기(int node,int start,int end,int L,int R){

        if(end < L || R < start) return 0; // 찾는범위가 아닌경우

        if(L <= start && end <=R){
            return tree[node];
        }else {
            int mid = (start+end)/2;
            return 구간합찾기(node*2,start,mid,L,R)
                    +구간합찾기(node*2+1,mid+1,end,L,R);
        }
    }

    public void 변경된요소_업데이트(int node, int start, int end, int idx, int diff){
           if(idx < start || idx > end) return;
           tree[node] = tree[node] + diff;
           int mid = (start+end)/2;
           if(start != end){
               // 리프노트는 이미 변경된 상태이므로 변경할 필요없음!

               변경된요소_업데이트(node*2,start,mid,idx,diff);
               변경된요소_업데이트(node*2+1,mid+1,end,idx,diff);
           }
    }
}

 

 

출처 : www.acmicpc.net/blog/view/9

세그먼트 트리 (Segment Tree)