이 섹션에서는 세그먼트 트리가 무엇인지 볼 것입니다. 이에 대해 논의하기 전에 한 가지 문제를 살펴보겠습니다.
배열 arr[0,…,n-1]이 있다고 가정하고 다음 작업을 수행할 수 있습니다. -
-
인덱스 l에서 r까지 요소의 합을 찾습니다. 여기서 0 ≤ l ≤ r ≤ n-1
-
배열의 지정된 요소 값을 새 값 x로 변경합니다. 우리는 arr[i] =x를 해야 합니다. 0 ~ n – 1 범위의 i.
세그먼트 트리를 사용하여 이 문제를 해결할 수 있습니다. 세그먼트 트리는 O(log n) 시간에 합계와 쿼리를 얻는 데 도움이 될 수 있습니다. 이제 이것을 표현하는 방법을 살펴보겠습니다 -
-
리프 노드는 지정된 배열의 요소입니다.
-
각 내부 노드는 리프 노드의 일부 병합을 나타냅니다. 병합은 경우에 따라 다를 수 있습니다. 여기서 병합은 노드 아래의 잎의 합입니다.
[1, 3, 5, 7, 9, 11]과 같은 배열이 있다고 가정합니다. 따라서 세그먼트 트리는
