세그먼트 트리(Segment Tree) 자료구조는 누적 합 알고리즘의 심화 버전으로 이해될 수 있다. 크기가 N인 배열이 주어졌을 때, 누적 합 알고리즘의 시간복잡도는 O(N)이다. 이도 빠르긴 하지만, N의 크기가 더 커졌을 경우에는 이 또한 시간 초과가 나올 수 있다. 세그먼트 트리라는 완전 이진 트리 형태의 자료구조를 사용하면 배열의 특정 구간의 합을 구하는 시간복잡도는 O(logN)으로 훨씬 더 시간을 단축할 수 있다. 배열의 크기가 N일 경우의 세그먼트 트리의 형태은 다음과 같다. 하나의 노드마다 인덱스 i~인덱스 j 사이인 배열 구간의 누적 합 결과값이 들어간다. 세그먼트 트리 만들기 완전 이진 트리는 배열을 통해 구현한다. 어떠한 부모 노드의 두 자식 노드들은 부모 노드의 인덱스를 idx라고..
