seojin0305 PS 블로그

이 글은 segment tree(이하 segtree)를 완벽히 이해했음을 전제로 진행하는 글입니다. Segment tree Segment Tree segment tree가 뭔가요? segment tree(이하 segtree)는 주어진 배열에서 특정 원소 수정 구간 단위 연산의 결과(ex: 구간 합, 구간 최댓값) 를 $O(logN)$에 수행하게 해주는 알고리즘입니다. 기본 원리 작동하 seojin0305-ps.tistory.com 왜 필요한가요? segtree는 특정 원소를 수정하는 데 $O(logN)$의 시간복잡도가 소요됩니다. 그러나 특정 원소가 아닌, 특정 구간에 해당하는 모든 원소를 수정할 경우 시간복잡도는 $O(LlogN)$으로 매우 커지게 됩니다. lazy segment tree는 이를 $O(..

segment tree가 뭔가요? segment tree(이하 segtree)는 주어진 배열에서 특정 원소 수정 구간 단위 연산의 결과(ex: 구간 합, 구간 최댓값) 를 $O(logN)$에 수행하게 해주는 알고리즘입니다. 기본 원리 작동하는 기본 원리는 이분 탐색과 비슷한 듯 다릅니다. 위의 그림에서와 같이, 현재 구간에 대해 반으로 나누며 필요한 경우 새로운 구간에 대해 재귀적으로 반복하는 것입니다. 각 범위별로 구간 단위 연산의 결과를 저장해놓는다 하면, 배열의 크기가 $N$일 때 $4N$ 이하의 크기의 배열에 저장할 수 있습니다. 저장 원리는 현재 범위를 저장할 번호가 $k$라 할 때, 앞쪽 절반 배열은 $2k$, 뒤쪽 절반 배열은 $2k+1$에 저장하는 것입니다. 예시로 배열의 크기가 8이라 하..