[2021/09/02][짤막한 이야기 - 인덱스 트리]

[2021/09/02][짤막한 이야기 - 인덱스 트리]
“인덱스 트리(IndexTree)”는 이진 트리로 구성되는 연산 용이성을 목적으로 하는 자료구조이다.
앞선 포스트에서 구간합을 이야기하면서 구간합을 구하고 싶은 배열 A 내의 숫자가 변경될 수 있는 경우,
합배열을 모두 업데이트해야 할 수 있어 시간 복잡도가 크게 늘어날 수 있다고 하였다.
그러나 인덱스 트리로 부분합을 저장한다면 숫자가 변경되어도 부분합이 변경되어야 하는 횟수가 크게 줄어든다.
즉, 이진 트리(= 인덱스 트리) 내 부분합 업데이트는 O(logN)에 처리되기 때문에 합배열 업데이트가 O(N)으로 처리될 때보다 크게 시간복잡도가 줄어든다.
이 상태에서 A[3] ~ A[8]의 합을 물어보게 된다면 A[3] + A’’[1] + A[8]을 반환하면 된다.
이진 트리이기 때문에 전체 메모리 사용량은 합배열을 사용할 때와 동일하게 사용((A배열 크기) * 2)한다.
원래는 A배열을 2^K로 확장하여 0을 채우는게 정석(즉, A[0] ~ A[15])이라고 하지만, 본 포스트에서는 해당 과정은 생략하였다.
[관련된 짤막한 이야기 - 구간합(응용)[2021/08/13]]
#이야기 #루니프 #알고리즘 #자료구조 #인덱스트리 #이진트리 #구간합

[2021/09/02][Short Story - Index Tree]
“Index Tree” is a data structure for the purpose of ease of operation composed of a binary tree.
In the previous post about the prefix sum, if the number in array A for which you want to obtain the prefix sum can change, it may be necessary to update all values of the sum array, which can greatly increase the time complexity.
However, if the subtotal is stored as an index tree, the number of times the subtotal needs to be changed is greatly reduced even if the number changes.
That is, since the subtotal update in binary tree (= index tree) is processed in O(logN), the time complexity is greatly reduced compared to when the sum array update is processed in O(N).
In this state, if the sum of A[3] ~ A[8] is asked, it is enough to return A[3] + A’’[1] + A[8].
Since it is a binary tree, the total memory usage is the same as when using the sum array((size of A array) * 2).
Originally, it is said that it is normal to expand the A array to 2^K and fill in 0 (ie, A[0] ~ A[15]), but in this post, the corresponding process is omitted.
[Related Short Story - Prefix Sum(Application)[2021/08/13]]
#Story #LootNiP #Algorithm #DataStructure #IndexTree #BinaryTree #PrefixSum