Lazy propagation 안쓰고 구간 업데이트 쿼리 처리하기

일반적인 구간 업데이트 쿼리 처리 문제는 Lazy propagation을 구현한 세그먼트 트리로 풀 수 있다.

좀 더 특수한 경우의 문제로 먼저 구간 업데이트 쿼리가 쭈~욱 주어지고, 업데이트 쿼리의 중간에는 다른 쿼리를 처리할 필요가 없는 문제를 생각할 수 있다.

이런 경우의 문제는 구간 업데이트 쿼리를 각각

$O(1)$ 에 처리할 수 있다.

길이

$N$ 인 배열

$A$ 가 주어졌다고 하자. 편의상 인덱스를

$1 \sim N$ 으로 쓰고

$A[0]$ 에는

$0$ 이 들어있다고 생각하자. 그리고 다른 배열을 정의하겠다.

$S[i]$ : 구간 업데이트 쿼리에 의해

$A$ 의

$[l, \infty]$ 에 일정하게 더해진 값

$P[i]$ :

$A[0]$ ~

$A[i]$ 의 구간합

만약

$S$ 를 알고 있다고 하면

$P[0] = 0$

$P[i] = P[i - 1] + S[i] + A[i]$

가 된다.

$S$ 는 구간 쿼리가 구간

$[l, r]$ 에

$x$ 를 일정하게 더해라는 식으로 들어오면

$S[l]$ 에

$x$ 를 더하고

$S[r + 1]$ 에

$x$ 를 빼서 처리할 수 있다.

설명하려고

$S$ 와

$P$ 를 따로 썼지만 실제 구현에서는 하나의 배열로 처리해도 무방하다.

--------------------------------------------------------------

algoshipda의 블로그