Algorithm
세그먼트 트리(Segment Tree)
세그먼트 트리여러 개의 데이터가 존재할 때 특정 구간의 합(최솟값, 곱 등)을 구하는데 사용하는 자료구조이다.트리 종류 중 하나로 이진 트리의 형태이며, 특정 구간의 합을 가장 빠르게 구할 수 있다.시간 복잡도는 O(logN)언제 사용할까 ?0123456789위와 같은 배열에서 2부터 8까지의 데이터를 더하려면 범위의 원소를 하나씩 다 더하면 된다.이러한 방식으로 다른 특정 구간의 합을 구한다고 고려했을 때 앞에서 하나씩 더하므로 데이터의 갯수가 N이면 시간 복잡도는 O(N)이다.따라서, 이러한 방식으로 구간의 합을 구하면 속도가 너무 느리기 때문에 더 좋은 방법이 필요하다.이 때, 더 좋은 방법은 세그먼트 트리(Segment Tree)를 사용하는 것이다. 세그먼트 트리란 ?맨 밑(leaf) 노드는 자기..
