공부/자료구조 (1) 썸네일형 리스트형 인덱스 트리 (Binary Indexed Tree) 1. 정의 인덱스 트리는 원소들의 구간 합을 빠르게 구하기 위해 사용하는 자료구조로 펜윅 트리라고도 한다. 세그먼트 트리와 같이 기능을 하지만 구현이 좀 더 쉽고 직관적이며 많은 문제에 활용할 수 있다. 인덱스 트리는 원소를 업데이트(Point update)하거나 구간 합(Range query)을 구하는 데 걸리는 시간은 $O(logN)$이다. 2. 구현 1) 배열 크기 설정 인덱스 트리는 포화 이진트리로 먼저 배열의 크기를 구해야 한다. 단순히 배열에 원소만 들어가는 것이 아니라 원소들의 구간합 정보가 배열에 포함되어야 한다. 인덱스 트리의 리프 노드에 원소가 저장이 되어야 하고, 리프 노드부터 루트 노드까지 각각의 부모 노드는 자식 노드들의 합이 저장되어야 한다면 구현에 필요한 노드의 개수 즉, 인덱.. 이전 1 다음
