세그먼트 트리(Segment tree)

1. 개념 정리

1) 여러 개의 데이터가 연속적으로 존재할 때 특정 구간의 데이터의 합을 담은 이진 트리

2) 실제 구현은 트리가 아닌 배열로 하게 된다.

- 배열은 인덱스가 있어 접근성이 좋기 때문이다.

3) 세그먼트 트리를 이용한 구간 합 처리의 시간 복잡도는 O(lgn)이다.

 

2. 예시

1) 구간 합의 데이터가 될 배열을 준비한다.

int[] arr = {1,2,3,4,5,6,7,8};

2) 구간 합 트리가 될 배열도 준비한다.

int[] tree = new int[32]; // arr.length * 4
// 데이터의 개수가 N개일 때 필요한 부분 합 트리의 공간은
// N 이상의 2의 거듭제곱수 중 가장 작은 것 * 2이다.
// 여기서 N=8이므로 8 이상의 2의 거듭제곱수 중 가장 작은 것은 8이고
// 8 * 2 = 16개의 공간이 필요한데 매번 2의 거듭제곱을 계산하기 번거롭기 때문에
// 이를 계산하지 않고 커버가 가능하게 데이터의 개수 * 4를 주로 사용한다.

3) 구간 합 트리는 인덱스 1부터 사용할 것이고, 각 노드에 들어가게 될 값은 다음과 같다.

// create()를 재귀호출함으로써 tree를 완성한다.
// arr의 값 변경이 즉각적으로 tree에 영향을 미치지 않게끔 구간 합 트리를 완성한다.
					tree[1]=36;
		 tree[2]=10; 					tree[3]=26;
     tree[4]=3;		     tree[5]=7; 	     tree[6]=11; 	  tree[7]=15;
tree[8]=1; tree[9]=2; tree[10]=3; tree[11]=4; tree[12]=5; tree[13]=6; tree[14]=7; tree[15]=8

 - 구간 합 트리의 인덱스를 1부터 쓰는 이유는, 인덱스*2를 하면 해당 노드의 왼쪽 자식이 나와 접근이 편하기 때문이다.

4) arr에서 인덱스 2~6 범위의 데이터의 합을 구한다고 하면 아래 색칠한 노드만 방문하면 된다.

// 일반적인 접근             // 세그먼트 트리를 이용
int sum = 0;		    // sum()을 호출하여 계산
for(int i=2 ; i<=6 ; i++)   // tree의 인덱스 5, 6, 14번에 접근하면 되겠군!
    sum += arr[i];         sum = tree[5] + tree[6] + tree[14];
System.out.print(sum);      // 7 + 11 + 7 = 25
// 25

5) arr[4]의 값을 5 -> 10으로 변경한다면 아래 색칠된 노드를 방문하며 값에 +5를 해주면 된다.

// arr[4] = 5 -> 10으로 변경
// update()를 호출해 구간 합을 변경하자.
tree[1]=36+5;
tree[3]=26+5;
tree[6]=11+5;
tree[12]=5+5;

 

3. 구현 코드

// 1. 메서드 구현

// node: 구간 합 트리의 노드 인덱스. root 노드는 1
// start, end: 노드 인덱스가 node인 노드의 구간 합 인덱스. root 노드는 전체 구간

// 구간 합 트리 생성
static int create(int[] d, int start, int end, int node) {
    if(start==end) // leaf node
        tree[node] = d[start];
    else { // 반으로 나눠서 두 자식의 합을 tree[node]에 할당
        int mid = (start+end)/2;
        tree[node] = create(d, start, mid, node*2) + create(d, mid+1, end, node*2+1);
    }  // node*2: node의 왼쪽 자식, node*2+1: node의 오른쪽 자식
    return tree[node];		
}

// [left, right] 범위의 데이터의 합 반환
static int sum(int start, int end, int node, int left, int right) {
    if(right<start || left>end) // 구간 합 인덱스가 [left, right]와 맞지 않으면
        return 0;

    if(left<=start && end<=right) // 구간 합 인덱스가 [left, right] 내에 들어간다면
        return tree[node];

    // 구간 합 인덱스가 [left, right]가 걸쳐 있다면 왼쪽 오른쪽으로 나눠서 구하기
    int mid = (start+end)/2;
    return sum(start, mid, node*2, left, right) + sum(mid+1, end, node*2+1, left, right);
}

// [start, end]에서 index를 포함하는 구간 합 트리의 node 값에 dif를 더한다.
static void update(int start, int end, int node, int index, int dif) {
    // index가 [start, end] 내에 없을 경우
    if(index<start || end<index) return;
    
    // [start, end] 안에 있으면 dif를 더하고, 아래로 내려가며 다른 노드의 값도 변경
    tree[node] += dif;
    if(start==end) return; // leaf node면 중지

    int mid = (start+end)/2;
    update(start, mid, node*2, index, dif); // 왼쪽 자식 방문
    update(mid+1, end, node*2+1, index, dif); // 오른쪽 자식 방문
}

// 2. 메서드 사용 예시

// 구간 합 트리를 클래스 변수로 선언
static int[] tree;
	
// main()
// 1) 구간 합의 데이터가 될 배열을 준비한다.
int[] arr = {1,2,3,4,5,6,7,8};
int n = arr.length;

// 2) 구간 합 트리가 될 배열도 준비한다.
tree = new int[n*4];

// 3) 구간 합 트리는 인덱스 1부터 사용할 것이고,
// create()를 호출해 각 노드에 들어가게 될 값을 채운다.
create(arr, 0, n-1, 1);
    	
// 4) arr의 인덱스 2~6 범위의 데이터의 합을 sum()을 호출해 구한다.
System.out.printf("[2,6] 범위의 arr의 합= %d\n", sum(0, n-1, 1, 2, 6));

// 5) arr[4]의 값을 5 -> 10으로 변경한다면 인덱스 4를 포함하는 구간 값을 +5을 해주면 된다.
int newValue = 10;
int dif = newValue-arr[4];
arr[4] = newValue; // 이후에 또 값 변경이 될 것을 생각해서 arr도 바꿔놓기
System.out.printf("값 변경 이전 [2,6] 범위의 arr의 합= %d\n", sum(0, n-1, 1, 2, 6));
System.out.printf("값 변경 이전 [0,2] 범위의 arr의 합= %d\n", sum(0, n-1, 1, 0, 2));
update(0, n-1, 1, 4, dif);
System.out.printf("값 변경 이후 [2,6] 범위의 arr의 합= %d\n", sum(0, n-1, 1, 2, 6));
System.out.printf("값 변경 이후 [0,2] 범위의 arr의 합= %d\n", sum(0, n-1, 1, 0, 2));

// 위 코드에서 나온 printf문 5개의 출력 결과
[2,6] 범위의 arr의 합= 25
값 변경 이전 [2,6] 범위의 arr의 합= 25
값 변경 이전 [0,2] 범위의 arr의 합= 6
값 변경 이후 [2,6] 범위의 arr의 합= 30 // 인덱스 4의 값이 변경됐으므로 구간 합도 변경
값 변경 이후 [0,2] 범위의 arr의 합= 6  // 인덱스 4와 관계 없으므로 구간 합은 그대로