[Algorithm] Segment Tree

문제

Prefix Sum 배열을 이용하면 누적합을 O(n) 시간에 구할 수 있다.

=> O(logn)에 누적합을 구할 수 있는 방법은 없을까?

=> 배열을 수정할 수 있는 방법은 없을까?

 

Segment Tree 

- 완전 이진 트리이다. (배열로 표현할 수 있다.)

- 리프노드는 배열의 각 원소 값을 갖는다.

- 각 노드는 왼쪽 자식 노드와 오른쪽 자식 노드 값의 합을 갖는다.

- 노드의 개수는 배열의 요소 개수의 4배가 된다.

Segment Tree 생성 코드 (재귀)

합 구하기

각 노드가 나타내는 구간이 [start, end]일 때, [left, right] 합을 구하는 방법은?

 

루트부터 차례대로 다음을 점검한다. (4가지 경우의가 존재한다.)

 

1. [start, end]와 [left, right]가 겹치지 않는다.

=> 아무것도 하지 않는다.

 

2. [start, end]가 [left, right]에 포함된다.

=> 이전에 구한 해당 노드의 값. 즉 [start, end]의 합을 더한다.

+ 초기화 시 구해져 있다.

 

3. [start, end]가 [left, right]를 포함한다.

=> 두 자식 노드와 [left, right]에 대해 포함 관계를 파악한다. (재귀)

 

4. [start, end]가 [left, right]와 포함관계는 없지만, 겹친다.

=> 두 자식 노드와 [left, right]에 대해 포함 관계를 파악한다. (재귀)

[start, end] 합을 갖는 node부터 [left, right] 합을 구하는 코드

트리 수정하기

 

[start, end] 합을 갖는 node를 diff만큼 증가시키는 코드