BOBO's Note

세그먼트 트리는 어떠한 배열이 주어졌을 때, 각 구간의 대표값(예. 합, 최대값 등)을 빠르게 구할 수 있는 자료구조이다. 배열의 크기가 N일 때, 임의의 구간에 대한 쿼리를 O(logN)에 수행할 수 있다. 인덱스 트리는 팬윅 트리(Fenwick Tree)라고도 하며, 세그먼트 트리처럼 각 구간의 대표값을 빠르게 구할 수 있다. 세그먼트 트리보다 구현하기 더 간단하고 속도가 빠르다는 장점이 있다. 이 포스터에서는 구간합을 세그먼트 트리를 이용해 빠르게 구하는 방법에 대해 알아보자. 구간합 구하기 배열 arr[0], arr[1], ..., arr[N-1]이 있다고 할 때, 임의의 구간 [l, r]에 대하여 구간합 arr[l] + arr[l+1] + ... + arr[r-1] + arr[r]을 구해라. 위..