Lazy Propagation
Lazy Propagation 배열의 구간 쿼리, 구간 합을 빈번하게 수행할 때 비교적 적은 횟수로 쿼리를 수행하는 방법 Segment Tree, Fenwick Tree 활용의 연장선에 있다. 배열 X에서 구간 쿼리를 수행하고 구간 합을 구할 때 한 개의 트리만 사용할 경우 구간의 길이만큼 쿼리를 수행해야 한다. 이때 추가적인 트리를 사용하면 쿼리를 적은 횟수 수행하고 두 트리를 모두 사용해 구간 합을 구할 수 있다. 0으로 초기화된 배열 X에서 다음 구간 쿼리를 수행한다고 하자. [4,9]에서 +6 [3,6]에서 -2 두 세그먼트 트리/펜윅 트리 a, b를 아래와 같이 이용할 수 있게 update하자. 구간 [1,4]의 합을 구하는 경우, [1,4] 내에서 6은 X[4]에, -2는 각각 X[3], X[..
2021. 8. 13.
