구간합을 반복적으로 빠르게 계산하기 위해서 세그먼트 트리와 펜윅 트리를 이용한다. 세그먼트 트리와 펜윅 트리는 원래의 데이터 값을 저장하는 방법이 아니라, 이름에서 알 수 있듯 데이터를 구간별로 저장하는 형식을 가진다. 간단하게 말하여 부분합을 위하여 i번째까지의 데이터를 모두 합한 값을 유지하고 있다고 보면 된다. 세그먼트 트리는 리프노드에는 원래의 데이터를 그리고 그 부모 노드는 아래의 리프 노드들의 합을 저장하고 있다고 보면된다. 이러한 특징을 바탕으로 특정 구간의 값을 찾는 행위는 O(logN) 그리고 값을 변경 하는 행위 또한 O(lgN)만에 수행할 수 있다. 세그먼트 트리의 경우 필요 메모리량이 복잡하게 계산된다. Full binary tree의 경우 N이 2의 제곱꼴이면 2*N-1개의 노드가..