[알고리즘] 트리를 사용해서 구간합 구하기

1. 구간합

- 수들의 나열에서 특정 구간의 합을 의미한다. 구간 합 알고리즘은 보통 1차원 배열에서 i~k 인덱스 사이의 값들의 합을 구하는데 사용한다.

- 합배열을 사용해서 쉽게 구할 수 있다.

인덱스 2부터 4까지의 구간합을 구하기 위해서는 합배열의 인덱스 4에서 인덱스 1의 값을 빼면 된다.

하지만 이때 배열 A의 값이 업데이트 되는 경우, 배열 A의 합배열이 전부 변경되어야 하는 상황이 발생하게 된다. 

예시와 같이 7개짜리 배열이면 큰 문제가 되지 않지만, 배열의 크기가 클 수록 많은 값들이 변경되어야 한다.

이러한 경우 트리를 사용하여 구간합을 구할 수 있다.

 

트리를 배열로 구현하는 내용이 헷갈린다면 아래의 블로그를 참고하면 좋을 것 같다.

정리를 잘해두셔서 이해하기 좋다.

https://yoongrammer.tistory.com/69

[자료구조] 이진 트리 (Binary tree) 알아보기

 

2. 트리의 종류

구간합을 구하는 트리의 종류에는 인덱스 트리, 세그먼트 트리, 펜윅 트리(바이너리 인덱스 트리)가 있다.

인덱스 트리와 세그먼트 트리는 일반적으로 동일한 의미로 사용하는 것 같긴하지만, 인덱스 트리가 좀 더 넓은 개념이라고 생각하면 될 것 같다. 따라서 세그먼트 트리로 풀 수 있는 문제는 인덱스 트리로 모두 풀 수 있다.

펜윅트리의 경우구간 합에 특화되어 있으며 비트연산을 기반으로 하기 때문에 속도가 매우 빠르고 메모리 효율이 좋다는 장점이 있다. 하지만 세그먼트 트리처럼 최댓값, 최솟값, 곱 등의 다양한 연산을 처리하는데는 적합하지 않다.

 

특징은 대략적으로 아래와 같다

특징	인덱스 트리	세그먼트 트리	펜윅 트리
구조	완전 이진 트리	불완전 트리	비트 연산 기반 배열
탐색	특정 인덱스 탐색 용이	구간 탐색에 적합	구간 합 계산에 특화
업데이트	리프 노드부터 가능	반드시 루트 노드부터 구간 업데이트	특정 인덱스 값 업데이트
특정 구간 연산	O(log N)	O(log N)	O(log N)
구간 업데이트	O(N)	O(N)	지원하지 않음
메모리	2N 크기의 배열 필요	2N 크기의 배열 필요	N 크기의 배열 필요

 

3. 인덱스 트리

인덱스 트리가 작동하는 방식은 다음과 같다. 위의 예시를 이어서 생각해 봤을 때, 다음과 같은 완전이진트리가 만들어지는 것을 볼 수 있다. 전체 구간 중에 내가 구하고자 하는 범위가 걸쳐져 있다면 절반으로 나누어 왼쪽트리 + 오른쪽 트리의 합으로구하게 된다. 아래의 경우에는 절반으로 나누어 4와 2의 합인 6 그리고 3끼리 더해서 구간합을 구하게 된다.

만약 값을 업데이트가 하고 싶은 경우에는 연결된 노드들의 값만 변경된다.

 

 

레퍼런스

https://noteofdeveloper.tistory.com/63

알고리즘 인덱스 트리, 세그먼트 트리

https://beenii.tistory.com/156

인덱스 트리 (Indexed Tree)

https://minusi.tistory.com/entry/%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8-%ED%8A%B8%EB%A6%ACSegment-Tree-Index-Tree

세그먼트 트리(Segment Tree, Index Tree)

https://minusi.tistory.com/entry/%ED%8E%9C%EC%9C%85-%ED%8A%B8%EB%A6%ACFenwick-Tree-Binary-Indexed-Tree

펜윅 트리(Fenwick Tree, Binary Indexed Tree)