인덱스트리

인덱스 트리 인덱스 트리는 값이 계속 변경되는 구간의 대표값을 구할 때 쓰이는 자료구조이다. 여기서 대표값이란 구간의 합, 최솟값, 최댓값 등을 말한다. 이번 글에서는 구간의 합을 예시로 들어 설명하겠다. 인덱스 트리의 구조 인덱스 트리에서 부모 노드는 자식 노드의 대표값을 가진다. 아래와 같은 노드가 있다고 해보자. 이 노드들의 부모는 어떤 값을 가질까? 루트 노드까지 트리를 채워보자. 부모 노드는 자식 노드의 합이라는 것을 볼 수 있다. 여기서 주의해야 하는 점은 이진 트리의 각 계층은 2의 제곱수만큼 노드를 가져야 하는데, 우리 예시는 노드가 5개 뿐이다. 즉, 5보다 큰 2의 제곱수인 8보다 3개 모자르다. 따라서 현재 우리는 구간의 합을 구하는 문제이기 때문에 합에 영향을 끼치지 않는 0으로 채..