오늘은 구간합을 구할 때 효율적인 세그먼트 트리에 대해 알아보겠다. 1차원 배열로 표현이 가능해서 생각보다 간단하게 구현할 수 있고, 단계별로 이해하면 크게 어렵지 않게 이해할 수 있다. 모든 알고리즘이나 자료구조는 코드를 암기하는 것 보다 구조와 동작을 이해하는 것이 더 중요하다. 세그먼트 트리를 한 단계씩 파헤쳐보자. 세그먼트 트리 (Segment Tree)? 일단 세그먼트 트리를 먼저 알아보자.세그먼트 트리는 특정 구간의 합, 곱과 같은 연산을 포함하여 최댓값, 최솟값을 구하는 용도로 사용하는 자료구조이다. 비슷한 자료구조로 구간 합과 비슷하지만 시간복잡도도 우수하고 업데이트에도 용이하다. 세그먼트 트리를 이해하기 쉽게 몇 가지 특징을 먼저 알아보자. 그 다음 세그먼트 트리로 구간합을 구해보자.특징..
