indexed tree 썸네일형 리스트형 14. 인덱스 트리(Indexed Tree) 인덱스 트리는 순서를 갖는 정보들이 주었을 때, 구간의 대표값이나 연산 결과를 빠르게 얻을 수 있는 자료구조입니다. 구간의 정보를 빠르게 파악할 수 있는 이유는 정보들을 2진 트리로 구성하여 두 개 노드의 부모노드에 대표값이나 연산결과를 저장했다가 구간이 주어졌을 때 최대한 커버가 가능한 구간 정보부터 압축적으로 정보를 추출하기 때문입니다. 아래와 같이 8개의 정보를 갖고 있는 배열이 주어졌다고 해봅시다. 1 ~ 8자리까지 각 배열의 자리에는 랜덤한 숫자가 주어져 있고 우리는 구간이 주어졌을 때 그 구간의 합이 얼마인지 알고 싶습니다. 1 2 3 4 5 6 7 8 3 2 8 1 2 3 5 6 만일 구간의 합을 구한다고 했을 때 단순하게 계산한다고 하면 매번 그 범위 내에서 for문을 이용하여 합을 구해야.. 이전 1 다음