배열의 부분합을 구할 떄 사용하는 자료구조 일반적인 for으로 구현하면 N이 리스트의 길이일떄 O(N)의 시간복잡도로 계산 가능하지만 세그먼트 트리를 사용하면 O(logN)으로 가능하다. 초기화 과정 O(logN) 출력 O(logN). 세그먼트 트리는 크게 두가지 함수가 존재한다. 하나는 주어진 정수 리스트를 바탕으로 세그먼트 트리를 만드는 init함수와 만든 세그먼트 트리를 이용해 특정 구간합을 반환하는 query함수이다. 구체적인 구현은 아래와 같다. 세그먼트 트리는 이진 트리로 루트, 왼쪽자식, 오른쪽 자식으로 구성되어있다. 한편 세그먼트 트리를 구성하는 leaf 노드를 제외한 모든 정점의 값은 해당 정점을 중심으로 왼쪽 자식과 오른쪽 자식으로 합이고 리프노드의 자리에는 주어진 정수 리스트의 값이 ..