indexed tree1 인덱스 트리 (Indexed Tree) 구간합을 구하는 트리 종류에는 인덱스 트리, 세그먼트 트리, 펜윅 트리가 있습니다. 그 중에서도 오늘은 인덱스 트리(Indexed Tree) 에 대해 알아보려 합니다. 참고로, 인덱스 트리에 포함되어 있는 종류 중 하나가 세그먼트 트리이기 때문에 세그먼트 트리로 풀 수 있는 문제는 인덱스 트리로 모두 풀 수 있습니다. 인덱스 트리는 A라는 수열에서 구간 S ~ E 가 주어졌을 때, A의 구간 S ~ E 사이의 합을 구하기 위해 사용합니다. 중간 중간 A의 값이 하나씩 바뀔 때마다 그 구간의 합을 구할 때 인덱스 트리를 사용할 수 있습니다. 구현 과정을 보면 다소 복잡해 보일 수 있지만, 그래도 천천히 단계를 밟으면 쉽게 이해할 수 있습니다. 저는 Swift로 구현을 해볼건데요, 마지막에 Java 로 구현.. 2021. 3. 24. 이전 1 다음
