자료구조

인덱스 트리(Indexed Tree)는 N개의 데이터를 사용하여 2N크기의 이진 트리를 생성하고 각 범위를 대표하는 값(최대, 최소, 누적합 등)을 이진트리 형태로 저장하여, 이후에 한 구간 l, r에 대한 대표값을 O(log2(N))만에 구할 수 있게 해주는 형태다.

세그먼트 트리는 인덱스 트리와 비슷한 구조를 가지지만, 추가적인 공간을 활용하여 좀 더 복잡한 형태의 대표값(0이 아닌 값, 1인 비트의 수, 등)을 표현할 수 있을 뿐만 아니라 가장 큰 차이점은 동시에 구간적인 변화가 일어나도 이를 O(log2(N))만에 처리가 가능