[Java] 세그먼트 트리 Segment Tree

Goal

• Segment Tree에 대해 초심자에게도 설명할 수 있도록
• Segment Tree 장, 단점 파악
• Segment Tree 구현

 

 

Abstract

세그먼트 트리(Segment Tree)는 주어진 배열에 대한 구간 쿼리를 효과적으로 수행하기 위한 자료 구조 입니다. 주로 배열의 구간 합, 최소값, 최대값 등을 빠르게 계산하는 데 사용됩니다. 이 구조는 특히 배열이 자주 변경되는 경우에도 효과적입니다. 

 

세그먼트 트리는 트리 구조이며, 각 노드는 배열의 일부 구간에 대한 정보를 저장합니다. 각 노드는 자식 노드들의 정보를 조합하여 부모 노드에 저장된 정보를 갱신합니다. 트리 구조이기때문에 이러한 갱신의 시간 복잡도는 O(logN) 입니다.

 

 

 

Why Learn?

보통 많은 알고리즘 문제들은 10초 이내에 작업이 수행되도록 문제를 내곤합니다. 만약, 배열의 크기인 N값이 10만이고 구간에 대한 변경 이 꾸준하게 있으며 구간 합 or 최소값 or 최대값 을 요구하는 문제의 경우 트리 구조를 사용하지 않는다면 시간복잡도는 O(N^2)인 10만 x 10만으로 1초에 1억번 연산을 한다는 가정하에 100초 정도의 시간이 걸리게 됩니다. 

 

이는 문제에서 요구하는 시간초를 넘어가기 때문에 효율성 부분에서 감점이 될 것 입니다. 이러한 문제에서 필요한 알고리즘 바로 세그먼트 트리입니다. 세그먼트 트리는 해당 문제를 O(NlogN)으로 문제를 해결하기 때문에 0.005초가 걸리게됩니다.

 

N값이 10만인 경우 100초와 0.005초의 차이가 납니다. 이는 N값이 커질 경우 더 큰 시간 차이를 보입니다. 그렇기때문에 꼭 배워야하는 알고리즘입니다.

 

 

 

Process

1. leaf 노드부터 문제에 의도에 맞는 값을 부모노드로 최신화 시키며 트리를 구성합니다. (합, 최대값, 최소값)
2. 최신화할 값이 있다면 해당 노드부터 루트노드까지 최신화 시켜줍니다.
3. 합, 최대값, 최소값을 구하는 구간만큼 트리에서 가져옵니다.
4. 2~3 번을 반복합니다.

 

 

Code (Java)

// 구간합을 최신화하며 값을 구해오는 구조
class SegmentTree{
        long tree[];	// 1.
        int treeSize;

	// 2.
        public SegmentTree(int arrSize){
            int h = (int) Math.ceil(Math.log(arrSize)/ Math.log(2));

            this.treeSize = (int) Math.pow(2,h+1);
            tree = new long[treeSize];
        }
		
        // 3.
        // node: 현재 노드 위치
        // start: 시작 인덱스, end: 끝 인덱스
        public long init(long[] arr, int node, int start,int end){
            
            if(start == end){
                return tree[node] = arr[start];
            }

            return tree[node] =
            init(arr,node*2,start,(start+ end)/2)
            + init(arr,node*2+1,(start+end)/2+1,end);
        }
		
        // 4.
        // node: 현재 노드 위치
        // start: 시작 인덱스, end: 끝 인덱스
        // idx: 구간 합을 수정하고자 하는 노드
        // dif: 수정할 값
        public void update(int node, int start, int end, int idx, long diff){
            if(idx < start || end < idx) return;

            tree[node] += diff;

            if(start != end){
                update(node*2, start, (start+end)/2, idx, diff);
                update(node*2+1, (start+end)/2+1, end, idx, diff);
            }
        }
		
        // 5.
        // node: 현재 노드 위치
        // start: 시작 인덱스, end: 끝 인덱스
        // left, right: 구간 합을 구하고자 하는 범위
        public long sum(int node, int start, int end, int left, int right){
            if(left > end || right < start){
                return 0;
            }

            if(left <= start && end <= right){
                return tree[node];
            }

            return sum(node*2, start, (start+end)/2, left, right)+
                    sum(node*2+1, (start+end)/2+1, end, left, right);
        }
    }
}

1. 트리 구조에서 값을 최신화시킬 배열이다.
2. 트리를 적당한 크기로 생성하는 생성자이다. 2^h >= arrSize인 h 값을 찾아야 한다. log를 씌우고 +1 한값으로 배열의 크기를 정한다. (arrSize * 4)로 해도 무방하다. 
3. 재귀 형식이다. start=end이면 leaf 노드로 값을 채우고 아니라면 자식 노드에서 더한 값을 node에 최신화 시켜준다.
4. 모든 노드를 돌며, idx에 해당되는 node만 값을 수정해준다.
5. left와 right에 포함되는 노드의 값만 return 해주며 재귀형식으로 더해서 RETURN 해준다.

 

 

그림으로 이해하는 Segment Tree

이해를 위해서 그림은 링크를 참고하여 가져왔습니다.

 

init 함수

재귀 방식으로 leaf노드까지 간 뒤, 해당 노드의 값을 초기화 시키고 값을 return 해줍니다. return 된 자식 노드의 합을 현재 노드의 값으로 초기화 시켜주면서 root 노드까지 값이 초기화됩니다.

 

init 함수가 종료되면 아래와 같은 트리 형식을 배열로 값을 가지고 있다고 보면됩니다.

 

 

update 함수

만약, 4번째 값을 2에서 10으로 바꾼다고 가정합시다. 그렇다면 update 함수에서는 트리의 값을 어떻게 초기화 시킬까요?

위와 같은 작업이 이루어 집니다. idx가 start와 end 사이에 있다면 10-2만큼 값을 더해줍니다. 0~11, 0~5, 0~2(X), 3~5, 3~4, 3(X), 4, 5(X), 6~11(X) X표시 친 부분에서 함수 맨 위 조건문으로 return 되며 X표시 치지 않은 곳들은 값이 더해집니다.

 

 

sum 함수

만약, 8~11 값의 합을 구하는 상황이라면 sum 함수는 어떻게 동작할까요?

 

위와 같은 방식으로 동작합니다. 8~11인덱스에 포함되지 않은 구역은 0을 return, 8~11에 완전히 포함되어 있다면 현재 노드 값 Return, 완전히 포함되어 있디 않다면 포함된 구역만 찾기 위해 자식 노드를 탐색하여 더한 값을 return 합니다.

 

 

시간복잡도

N값이 배열의 크기고, K번 만큼의 update, sum 작업이 있다고 가정하면 O(KlogN)의 시간복잡도를 가질 것이다.

 

 

 

공간복잡도

N만큼의 int 혹은 long의 배열로 문제를 풀어내는 것보다는 많은 공간을 차지한다. 보통 N*4로 트리 배열의 크기를 사용한다고 가정한다면, N*3의 자료형만큼 더 많은 공간을 사용하게 된다.

 

 

 

장점

• 시간이 훨씬 빠르다. 

 

 

단점

• 구현이 복잡하다.
• 더 많은 공간을 사용한다.

 

 

결론

더 많은 공간을 차지하긴 하지만 시간복잡도에서 많은 우위를 점할 수 있는 알고리즘이다. 적절하게 사용하면 유용한 알고리즘이다.