자료 구조

자료구조, 세그먼트 트리(Segment Tree) [Python]

🦕 세그먼트 트리(Segment Tree)란? 세그먼트 트리는 배열에서 특정 구간에 대한 정보를 빠르게 쿼리하거나 수정할 수 있게 해주는 이진 트리 기반의 자료구조입니다. 이 자료구조는 주로 범위 쿼리 문제에 활용되며, 그 중에서도 구간 합을 빠르게 계산하는 데에 자주 사용됩니다. 원리 세그먼트 트리의 각 노드는 배열의 특정 구간을 대표합니다. 리프 노드는 배열의 개별 원소를 나타냅니다. 부모 노드는 자식 노드들의 합을 저장합니다. 이런 방식으로 트리의 루트 노드는 배열 전체의 합을 저장하게 됩니다. 예시 배열 A [1, 3, 5, 7, 9, 11]을 고려해봅시다. 이때 Tree 는 [0, 36, 9, 27, 4, 5, 16, 11, 1, 3, 7, 9] 가 됩니다. 각 노드에는 배열의 구간 합이 저장되..