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$를 따로 썼지만 실제 구현에서는 하나의 배열로 처리해도 무방하다.
--------------------------------------------------------------
댓글
댓글 쓰기