세그먼트트리1 Segment Tree(세그먼트 트리) (Python3) 세그먼트 트리란?세그먼트 트리는 구간의 정보를 알고 싶을 때 사용하는 트리입니다.각 노드는 자식 노드의 정보를 연산한 값을 저장하고 있습니다. 이 특징으로 구간의 사칙연산, 최대·최솟값 등을 구할 때 자주 사용한다고 합니다. 개발자는 배열 혹은 리스트에서 부분의 합 정보를 알고 싶습니다. 그래서 선형 탐색으로 접근을 하고, 구간이 일치한다면 그 정보들을 하나하나 가져옵니다. 이것은 구현이 쉬우나, O(N)의 비용이 발생합니다. 세그먼트 트리의 노드는 부분의 정보를 저장하고 있습니다.말단 노드(leaf node)에 접근하면, 배열의 원소 값과 일치합니다.하지만 말단 노드의 부모 노드 부터는, 자식 노드의 정보를 합한(혹은 빼거나 곱하는 등) 값을 저장하고 있습니다.그래서 필요한 구간의 노드를 찾아내면 원하.. 2025. 3. 29. 이전 1 다음
