세그먼트트리(구간합 트리)

구간합

  구간합이라는 것은 여러개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터 합을 구하는 것을 의미한다.

 

선형적으로 구간합 구하기

 

  인덱스 2부터 10까지의 구간합을 구한다고 하면 인덱스 2부터 10까지 계속 값을 더해가면 된다.

  이러한 방식이 선형적으로 구하는 방식이고 이 과정은 O(N)의 시간 복잡도를 갖는다.

 

  따라서 선형적으로 구간합을 구하는 것은 비효율적이므로 트리구조를 활용한다.

  트리구조를 활용하여 구간합을 구하는 과정은 O(logN)의 시간 복잡도를 갖는다.

 

구간합트리

  완전 이진트리를 이용한다. 완전이진트리는 루트부터 0, 1, 2... 순서로 내려가는데 데이터를 채워넣었다고 가정한다.

  구간합 트리의 구조는 다음과 같다.

  여기서는 루트를 1부터 시작한다고 가정했다.

  트리의 루트인 1번 인덱스는 값의 0번 인덱스부터 6번 인덱스까지의 합을 갖는다.

  트리의 2번 인덱스는 값의 0번 인덱스부터 3번 인덱스의 합

  트리의 3번 인덱스는 값의 4번 인덱스부터 6번 인덱스의 합을 가진다.

  이러한 형태로 계속 내려가게 되고 리프노드에서는 0번에서 6번까지의 값을 하나씩 갖는다.

  

  값을 넣어서 보면 위와 같은 형태가 된다. 자식노드의 합을 부모노드가 갖는 형태가 된다.

  그럼 최종적으로 루트노드는 모든 리프노드의 합을 값으로 갖게 된다.

 

  여기서 2-4의 구간합을 구한다고 하면

  루트노드는 0-6의 구간합을 모두 포함하고 있으므로 양쪽 자식노드로 내려간다.

 

  루트의 왼쪽자식노드에서는 0-3의 구간합을 갖고 있는데 원하는 구간은 2-4이므로 오른쪽 노드로만 내려간다.

  루트의 오른쪽자식노드에서는 4-6의 값을 갖고 있으니 왼쪽 노드로 내려간다.

 

  그럼 2-3의 구간합은 찾았고 4의 값을 찾기위해 6번인덱스의 노드에서 4의 값만 갖고 있는 리프노드로 내려간다.

  그럼 원하는 구간을 모두 찾은것이므로 5와 12가 채택되어 결과값을 출력하게 된다.

  이렇게 내려오는 높이는 logn이라고 할수 있기 때문에 logn만으로 구간합을 계산할 수 있게 되는 것이다.

 

구간합 수정하기

  만약 10번에 있는 2번 인덱스의 값을 수정한다면 그 상위노드 값을 모두 변경해줘야 한다.

 

 

예제코드

 

#include <stdio.h>
#define NUMBER 7

int a[] = { 7, 1 ,9, 5, 6, 4, 1 };
int tree[4 * NUMBER]; //모든 범위를 커버하기 위해 4를 곱한다.

//start : 시작인덱스, end : 끝 인덱스
int init(int start, int end, int node){
  if(start == end) return tree[node] = a[start];
  int mid = (start + end) / 2;
  
  //재귀적으로 두 부분을 나눈 뒤에 그 합을 자기 자신으로 한다.
  return tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
}

//start : 시작인덱스, end : 끝 인덱스
//left, right : 구간합을 구하고자 하는 범위
int sum(int start, int end, int node, int left, int right){
  //범위 밖에 있는 경우
  if(left > end || right < start) return 0;
  
  //범위 안에 있는 경우
  if(left <= start && end <= right) return tree[node];
  
  //그렇지 않다면 두 부분으로 나누어 합을 구한다.
  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 : 구간합을 수정하고자 하는 노드
//dif : 수정할 값
void update(int start, int end, int node, int index, int dif){
  //범위 밖에 있는 경우
  if(index < start || index > end) return;
  
  //범위 안에 있으면 내려가며 다른 원소도 갱신
  tree[node] += dif;
  if(start == end) return;
  int mid = (start + end) / 2;
  update(start, mid, node * 2, index, dif); //왼쪽방향으로
  update(mid + 1, end, node * 2 + 1, index, dif); //오른쪽 방향으로
}

int main(void){
  //구간합 트리의 인덱스를 제외하고는 모두 인덱스 0부터 시작한다.
  //구간합 트리 생성하기
  //초기셋팅으로 된 7개의 원소를 전부다 초기화해서 구간합 트리를 생성
  init(0, NUMBER - 1, 1); 
  
  //구간합 구하기
  printf("0부터 6까지의 구간합 : %d\n", sum(0, NUMBER - 1, 1, 0, 6));
  
  //구간합 갱신
  printf("인덱스 5의 원소를 +3만큼 수정\n");
  update(0, NUMBER - 1, 1, 5, 3);
  
  //구간합 다시 구하기
  printf("3부터 6까지의 구간 합 : %d\n", sum(0, NUMBER - 1, 1, 3, 6));
  
  system("pause");
}

  0부터 6까지의 구간 합 : 33

  인덱스 5의 원소를 +3만큼 수정

  3부터 6까지의 구간합 : 19

 

  이렇게 결과값이 잘 출력되는것을 확인할 수 있다.

  3부터 6까지 구간합은 16이었지만 19로 제대로 증가한것을 확인할 수 있다.

  확인을 위해서는 첫 출력문에서 0을 3으로 바꿔보면 3부터 6까지의 구간합을 확인할 수 있다.

 

 

레퍼런스

패스트캠퍼스 올인원 패키지 - 소프트웨어 베이직