목차 세그먼트 트리(Segment Tree)완전 이진 트리에 기반한 자료구조이다.고정된 크기의 수열에서 특정 구간의 질의 및 수정을 효율적으로 수행하기 위해 사용한다. 세그먼트 트리의 필요성길이 N=100만인 배열에서 특정 구간의 합을 구해야한다고 가정해보자. 최악의 경우는 아마, 전체 원소의 합을 구하는 경우일 것이다. 이는 O(100만)이 소요된다.수정의 경우는 어떨까? 해당하는 인덱스의 값을 변경하면 된다. 이는 O(1)이 소요된다. 세그먼트 트리를 사용한다면, 연산과 수정을 O(logN)에 수행할 수 있다. 즉, O(log100만=19.93)이다.합을 구하는 동작을 m번 수행한다면, 더 엄청난 차이가 발생할 것이다. 유의할 점이진수에 기반한 컴퓨터 과학에서, log의 밑은 e가 아닌 2를 의미한다..
