세그먼트 트리

기존 구간합을 구하기위해선 범위 안에 있는 모든 배열을 탐색해서 구해야하고 그 때마다 배열을 탐색해야한다.

 

하지만 세그먼트트리는 다이나믹프로그래밍의 일종으로 작은 단위부터 더해가서 각각 구간들의 합을 저장한다.

 

구간합은 Binary Tree 와 재귀를 사용해서 만들수가 있다.

 

구간합을 구하는 Tree 의 크기는 2^k >= N (n은 배열의 수) 를 만족하는 가장 작은 k값을 구하고

2^k *2 한것이 Tree의 크기가 된다. 생각하기싫은 N*4의 크기로 할당하면 된다.

 

 
public class Segment {
    static int arr[] = {3,5,6,7,2,9,4,5,2,8,1,5};
    static int node[];
    
    public static void main(String[] args) {
        int N = 12;
        
        //공간아 N*4 공간으로 활당한다 정확히는 2^k >=N 을 만족하는 k * 2 의 크기로 활당한다  여기서는 32
        //2 ^ (log2 (N) + 1 ) *2 하면  정확한 크기 연산가능
        
        node = new int[12*4];
        
        //init
        
        // 시작 인덱스, 끝인덱스 , 노드 번호
        Init(0,N-1,1);
        
        System.out.println(node[1]);
    
        
    }
 
    public static int Init(int start, int end, int n) {
        if(start==end) {
            return node[n] = arr[start];
        }
        
        
        
        int mid = (start + end) / 2;
        
        return node[n] = Init(start,mid,n*2) + Init(mid+1,end,n*2+1);
    }
}
 

 

부모의 노드 *2 -> 왼쪽 자식의 노드 , 부모의 노드*2+1 -> 오른쪽 자식의 노드이다.

 

    public static int sum(int start, int end, int i, int j, int n) {
        if (start == i && end == j) {
            return node[n];
        }
 
        int mid = (start + end) / 2;
 
        if (i <= mid && j <= mid) {
            return sum(start, mid, i, j, n * 2);
        } else if (i > mid) {
            return sum(mid + 1, end, i, j, n * 2 + 1);
        } else {
            return sum(start, mid, i, mid, n * 2) + sum(mid + 1, end, mid + 1, j, n * 2 + 1);
        }
 
    }

구간합 구하는 함수. 지관적으로 구할려는 i,j에맞게끔 재귀를 분리하였다. 찾아보니 더간결한 소스가 있어서 밑에 첨부.