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[4]에 더해져야 한다.

이 경우를 6을 4번 더했다가 3(=4-1)번 빼고, -2를 4번 더했다가 2(=3-1)번 뺀 것으로 생각해

구간 [1,4]의 합 = sum(a,4)×4+sum(b,4) 으로 구한다.

 

구간 [1,7]의 합은

6을 7번 더한 뒤 3(=4-1)번 빼고, -2를 4(=6-3+1)번 더하는 과정으로 생각해

sum(a,7)×7+sum(b,7) 로 구한다.

 

 

 

---

 

일반화하면

구간[1,k]의 합을 sum(a,k)×k+sum(b,k)으로 구할 수 있도록 a, b를 update해야 한다.

 

구간 [L,R]에 n을 더하면 구간 [1,k]의 합이 증가한 양은 아래와 같다.

(1) k≤R인 경우, n×k-n×(L-1)

(2) R<k인 경우, n×R-n×(L-1) 

 

 

여기서 k에 대한 update만 트리 a에 반영하고, 나머지는 트리 b에 반영하기 위해 아래와 같이 두 트리를 update한다.

update(a,L,n)  update(a,R+1,-n)

update(b,L-1,n×(1-L))  update(b,R+1,n×R)

 

(1)의 경우 k≤R이므로

update(a,L,n)만 k에 영향을 주고

update(b,L-1,n×(1-L))에 의해 -n×(L-1)을 구할 수 있다.

 

(2)의 경우 k>R이므로

update(a,R+1,-n)에 의해 n이 k에 영향을 주지 않고,

update(b,R+1,n×R)에 의해 n×R-n×(L-1)을 구할 수 있다. 

 

//add n to [L,R]
update(a, L, n); update(a, R + 1, -n);
update(b, L - 1, n * (1 - L)); update(b, R + 1, n * R);

//get sum of [1,k]
int s = sum(a, k) * k - sum(b, k);

---

 

위 두 쿼리에 대한 update는 아래와 같다.

[4,9]에서 +6

update(a,4,6) update(a,9+1,-6)

update(b,4-1,6×(1-4)) update(b,9+1,6×9)

 

[3,6]에서 -2

update(a,3,-2) update(a,6+1,2)

update(b,3-1,-2×(1-3)) update(b,6+1,-2×6)

 

remark: 구간 [5,7]의 합 = 구간[1,7]의 합 - 구간[1,4]의 합

 

 

---

 

배열 X가 0으로 초기화되지 않은 경우

X의 구간 합을 트리 x에 저장해 x, a, b 세 개의 트리를 사용해도 되지만

그 경우 X의 합을 구할 때 트리 x, a, b에 대한 sum함수를 모두 호출해야 한다.

배열 X의 구간 합을 x에 업데이트
트리 a, b를 각각 업데이트
⇒ X의 구간[1,k] 합 = sum(x,k) + sum(a,k)×k + sum(b,k)

 

트리 a에 대한 sum(k)에는 k를 곱해줘야 하므로 X를 a에 반영할 수는 없으니,

X를 x 대신 b에 업데이트하면 a, b 두 개만으로도 쿼리 수행이 가능하다.

배열 X의 구간 합을 b에 없데이트
트리 a, b를 각각 업데이트
⇒ X의 구간[1,k] 합 = sum(a,k)×k + sum(b,k)

 

 

---

 

10999번 구간 합 구하기 2

lazy propagation의 가장 기본형 문제인 듯

 

코드에서는 위 설명의 a, b대신 af, bf를 사용했다.

또한 쿼리함수 호출 시 트리를 같이 호출하는 대신 af, bf의 함수를 따로 정의했으며

upda, sumb 함수와 같이 구간 쿼리와 구간 합를 한 번에 해결할 수 있는 경우는 하나의 함수로 묶었다.

#include <iostream>
using namespace std;

typedef long long ll;

ll af[1000001], bf[1000001], N;
void upda(int i, int j, ll n) {
	while (i <= N) af[i] += n, i += (i & -i);
	while (j <= N) af[j] -= n, j += (j & -j);
}
ll suma(int i) {
	ll ret = 0;
	while (i) ret += af[i], i -= (i & -i);
	return ret;
}
void updb(int i, ll n) {
	while (i <= N) bf[i] += n, i += (i & -i);
}
ll sumb(int i, int j) {
	ll ret = 0;
	while (i) ret -= bf[i], i -= (i & -i);
	while (j) ret += bf[j], j -= (j & -j);
	return ret;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int M, K, q, L, R;
	long long n;
	cin >> N >> M >> K;
	for (int i = 1; i <= N; ++i) cin >> n, updb(i, n);
	while (M || K) {
		cin >> q >> L >> R;
		if (q & 1) {
			cin >> n; M--;
			upda(L, R + 1, n), updb(L, n * (-L + 1)), updb(R + 1, n * R);
		}
		else {
			ll s = sumb(L - 1, R) + suma(R) * R - suma(L - 1) * (L - 1);
			cout << s << "\n"; K--;
		}
	}
	return 0;
}

 

lazy propagation을 공부하겠다는 미루고 미뤄왔었던 계획을 드디어..

 

 

---

 

 

이 블로그 글을 참고했다. 👍👍👍