[Algorithm] 인덱스 트리(Indexed Tree)
구간 합을 구하는 트리의 종류로 인덱스 트리, 세그먼트 트리, 펜윅 트리가 있다. 세그먼트 트리는 인덱스 트리가 포함하고 있는 한 종류이다. 세그먼트 트리로 풀 수 있는 문제는 인덱스 트리로 모두 풀 수 있다. 인덱스 트리란 ? 이진 트리의 한 종류로서 구간 합을 구하는데 쓰이는 자료구조. 예를 들어, 배열 A에 수열이 들어있고 구간 S-E 가 주어졌을때 ① A[S] - A[E] 의 구간합을 구하고 ② 구한 뒤 특정 A[i]번째 원소가 다른 숫자로 바뀐다. ①② 번 작업을 반복하는 일이 있을 때 인덱스 트리를 쓰게 된다. 만약 1,2,3,4 라는 수열이 배열에 들어있다고 하면 수의 갯수를 모두 리프노드에 넣을 수 있을만큼의 배열을 잡아야한다. 아래 그림에서 4,5,6,7 번에 1,2,3,4 가 들어가면 ..
