Segment tree

Segment tree
세그먼트 트리
세그먼트 트리는 구간의 합, 구간의 최솟값, 구간의 최댓값등을 빠르게 구할 때 사용한다.
누적합과 비슷하다고 느낄 수 있지만 누적합은 합계를 구할 때에만 사용할 수 있다.
또 누적합은 하나의 값이 업데이트 된다면 해당 숫자 뒤의 모든 숫자가 모두 업데이트 되어야 한다.
세그먼트 트리는 구간내의 다양한 값들을 구할 수 있고, 업데이트 되더라도 몇개의 숫자만 업데이트 하면 되기 때문에 훨씬 유용하게 사용할 수 있다.
여러 개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터의 합을 구하는 방법.
트리 종류 중에 하나로 이진 트리의 형태이며, 특정 구간의 합을 가장 빠르게 구할 수 있다는 장점이 있다.

Segment tree - 시간 복잡도