📗 세그먼트 트리 배우기

1. 세그먼트 트리의 목적

길이가 $n$인 배열 $A$가 있을 때 $A_l + A_{l+1} + \dots + A_{r-1}+A_r$ 을 빠르게 구하고 싶다면 누적 합을 사용하면 된다. 누적 합 배열 $p$를 통해 $p_r - p_{l-1}$를 계산하여 $O(1)$만에 구간 합을 구할 수 있다.

<aside> ❓

그런데 만약 $A_i$ 의 값을 변경하면 어떻게 될까?

</aside>

변경 사항을 누적 합 배열에서 업데이트 하려면 $p_i,\ p_{i+1},\dots p_n$을 모두 업데이트 해야하기 때문에 $O(N)$이 걸린다.

세그먼트 트리를 사용하면 구간 합을 $O(logN)$, 값 업데이트를 $O(logN)$만에 할 수 있다.

2. 세그먼트 트리의 구조

구조는 다음과 같다.

• 세그먼트 트리는 완전 이진트리로 구성된다.
• 트리의 각 노드는 특정 구간의 원소들의 합을 저장한다.
• 노드에 $[l, r]$의 구간 합이 저장되어 있다면 노드의 왼쪽 자식은 $[l, m]$, 오른쪽 자식은 $[m+1,r]$의 구간 합을 저장한다.
• 리프노드는 $l=r$이다. 즉 배열의 값 $A_l$을 갖고 있는다.

값 업데이트는 업데이트 하려는 원소가 구간에 포함된 노드들을 모두 업데이트 한다.

• ex) $A_3$을 업데이트 한다면 $20, 10, 5, 2, 1$번 노드들을 모두 업데이트 하면 된다.

구간 합은 노드들을 적절히 조합하여 원하는 구간을 만든다.

• ex) $[5, 10]$의 구간합을 구하고 싶다면 $11, 6, 14$번 노드를 모두 더하면 된다.

3. 구현