인덱스 트리(Indexed Tree) 개념 및 구현
인덱스 트리 (Indexed Tree) 개념 인덱스 트리는 포화 이진 트리 모양의 자료 구조이다. 주로 구간의 최댓값이나 최솟값, 구간 합 등을 구할 때 사용한다. 리프 노드에 값을 저장하고, 부모 노드에 원하는 정보(최댓값, 최솟값, 합)를 저장한다. 배열을 순회하면서 원하는 정보를 계산할 수 있지만, 인덱스 트리를 사용하면 정보를 더 빠르게 구할 수 있다. 이미 계산한 정보가 있는 상황에서 배열이 변경되면 배열을 다시 순회해야 하지만, 인덱스 트리를 사용하면 정보를 더 빠르게 구할 수 있다. 따라서, 인덱스 트리는 1) 정보를 자주 구해야 하거나(query), 2) 배열이 자주 변경될 때(update) 사용하기 좋다. 인덱스 트리 구현 원리 인덱스 트리를 만드는 순서는 다음과 같다. 1. 리프 노드에..
알고리즘
2022. 9. 20. 16:18