개요취직해서 지금 당장 좋은 점 중 하나는 취직 전까지는 내가 하고 싶은 공부를 할 수 있다는 것이기도 하다.사실 옛날부터 세그트리에 대한 궁금증이 있었는데, 코테의 당락을 결정하지는 않을 알고리즘이라 미뤄두었던 기억이 나서 이번에 알아두려고 한다. 세그먼트 트리는 '여러 개의 데이터가 연속적으로 존재할 때, 특정 범위의 데이터의 합/곱/최대값/최소값 등을 구하는 방법'중 하나이다. 수열을 저장하는 배열 A가 존재한다고 가정했을 때, 다음과 같은 케이스를 생각해보자. (A) 구간 l, r (l 이 경우 시간복잡도는 O(N)이다. 누적합, 구간합을 구해놓은 후 특정 구간의 합은 O(1)에 도출할 수 있기 때문이다. (B) 구간 l, r (l 이전 케이스와 다르게, 한번 구해놓은 누적합을 재사용할 수..