세그먼트 트리(Segment Tree)

세그먼트 트리(Segment Tree)란?

특정 구간 내 데이터에 대한 연산(쿼리)을 빠르게 구할 수 있는 트리 를 말한다.

기본적으로 세그먼트 트리를 이진 트리 구조를 가진다.

구간합을 빠르게 구하기 위해 세그먼트 트리를 사용하고자 한다면, 리프 노드에 주어진 노드 값을 저장하고, 부모 노드부터 루트 노드까지 자식 노드의 합을 저장하여 세그먼트 트리를 구성할 수 있다.
→ 다음 코드를 참고하자

세그먼트 트리의 장점은 구간 데이터에 대한 연산을 빠르게 할 수 있다는 것이다.
기본적으로 구간 내의 데이터를 모두 조회하여 계산하는 O(N)보다 더 빠르다. (아래 시간복잡도 참고)

 

시간복잡도

• 데이터 변경: O(logN)
• 연산: O(logN)
• 데이터 변경할때마다 M번 연산: O((logN +logN)*M) = O(MlogN)

 

어떤 경우에 사용할까?

• 구간의 합을 구하는 경우
• 구간의 최댓값을 구하는 경우
• 분할 정복으로 풀리는 문제에 구간 쿼리가 많이 주어져서 구간마다 반복적으로 풀어야하는 경우

 

구현 방법

1. bottom-up 방식 (반복문)
2. top-down 방식 (재귀 호출)
   top-down 방식은 아래 블로그에 잘 설명이 되어있다.
   https://m.blog.naver.com/ndb796/221282210534

 

구현 (bottom-up 방식)

1. 구간 합 트리 생성하기 (Build)

ST는 리프 노드를 제외한 세그먼트 트리의 크기이다.
노드의 개수보다 크면서 2의 제곱인 수를 넣어준다.

seg 배열

• 0 ~ ST-1 : 구간합
• ST+1 ~ ST+n : 노드

 

• 노드 값 입력
• 세그먼트 트리의 리프노드부터 루트 노드까지 구간합을 구하면서 올라감

void build() {
	
    // 세그트리의 리프 노드를 채운다 (ST+1부터 노드)
    // 노드 값은 x라고 가정
    for (int i=1; i<=N; i++) {
    	seg[ST+i] = x; // 세그트리의 리프 노드 중 i번째 위치
    }
    
    // 역순으로 세그트리의 내부 노드를 채운다 (bottom-up)
    for (int n=ST-1; n>0; n--) {
    	seg[n] = seg[n*2] + seg[n*2+1];
    }
}

 

2. 구간 합을 구하는 함수 (Sum)

l(left), r(right) 은 최종적으로 구하고자 하는 구간의 범위
nl(node left), nr(node right) 은 현재 노드의 구간의 범위

• 해당 구간 안에 있으면 세그먼트 트리의 값 리턴
• 해당 구간 밖에 있으면 무시
• 해당 구간에 걸쳐져있으면, 분할하여 구한 뒤 합침

int query(int n, int nl, int nr, int l, int r) {
	
    // 구간 밖에 있는 경우
    if (nr < l || r < nl) return 0; 
    
    // 구간 안에 있는 경우
    if (l <= nl && nr <= r) return seg[n];
    
    // 구간에 걸쳐져있는 경우
    int mid = (nl+nr+1) / 2;
    return query(n*2, nl, mid-1, l, r) + query(n*2+1, mid, nr, l, r); // 분할된 문제를 합침
}

 

3. 특정 원소의 값 수정하는 함수 (Update)

• 특정 위치의 노드 값을 변경
• 변경된 노드의 부모 노드부터 루트 노드까지 올라가면서 업데이트

void update(int i, int val) {
  int n = ST+i; // 세그트리의 리프 노드 중 i번째 위치
  seg[n] = val;
  for (n /= 2; n >= 1; n /= 2) { // n /= 2를 통해 부모 노드를 타고 올라감
    seg[n] = seg[n*2] + seg[n*2+1];
  }
}

 

참고한 블로그

• https://cano721.tistory.com/38