구간트리

구간트리(Segment Tree)는 저장된 자료들을 적당히 전처리하여

특정 구간에 대한 질의를 빠르게 대답할 수 있도록 하게 하는 기법입니다.

보통 원소의 값 변경이 자주 일어나며 구간 원소의 합, 곱, 최댓값, 최솟값을 반복적으로 구해야 할 때 사용합니다.

구간에 대한 질의를 답할 때의 시간복잡도는 O(lgN), 원소 하나의 값이 변경 되었을 때의 시간복잡도는 O(lgN)이며

길이가 K인 구간의 원소의 값이 변경 되었을 경우의 시간복잡도는 O(KlgN)입니다.

이를 O(lgN)만에 하게 하기 위하여 레이지 프로퍼게이션(Lazy Propagation)기법을 사용합니다.

또한 앞서 배운 비트마스크 기법을 응용하여 짧고 간단하게 구간 합을 구할 수 있는 팬윅트리(Fenwick Tree)를 이용하여 

구간 합을 응용하여 푸는 문제를 좀 더 간편하게 구현 할 수 있습니다.

기본 문제

2042번: 구간 합 구하기

10868번: 최소값

10999번: 구간 합 구하기 2