segment tree (1) 썸네일형 리스트형 158. Segment Tree 알고리즘 문제를 풀 때 가장 자주 등장하는 자료 구조 중 하나인 세그먼트 트리(Segment Tree)에 대해 다룬다. 먼저 누적합을 다루면서 소개했던 구간 합 구하기 4 문제를 다시 보자. 수 $n$개가 주어졌을 때, $i$번째 수부터 $j$번째 수까지 합을 구하는 프로그램을 작성하시오. 이 문제에서 주어지는 쿼리는 아래와 같다. $i\ j$: $i$번째 수부터 $j$번째 수까지의 합을 출력한다. 수의 개수 $n$과 쿼리의 개수 $m$의 최댓값이 $10^5$이므로 누적합을 전부 구한 다음 각 쿼리를 $\Theta(1)$에 처리하면 $\Theta(n + m)$에 전체 문제를 해결할 수 있었다. 이제 쿼리를 하나 더 추가하자. $1\ x\ y$: $x$번째 수를 $y$로 바꾼다. $2\ x\ y$: $x$.. 이전 1 다음
