lazy propagation을 펜윅 트리로 풀기

먼저 모든 lazy propagation 문제를 펜윅트리로 풀 수 있는 것은 아니다.

하지만 lazy propagation 문제 중 대표적인 유형 몇 개는 놀랍게도 펜윅으로 풀 수 있다.

여기서는 두 문제를 소개하려고 한다.

이 놀라운 방법은 다음 두 곳에서 설명하는 것으로 이해했다.

 

www.acmicpc.net/blog/view/88

tony9402 님의 boj10999 풀이

 

먼저 대표적인 유형

www.acmicpc.net/problem/10999

10999번: 구간 합 구하기 2

이 문제를 보자.

문제를 간단하게 설명하면 두 가지 연산이 주어진다.

$A_1, A_2, ... , A_n$ 의 수가 있을 때

1. $A_l, A_l+1, ... , A_r$ 에 각각 k만큼 덧셈

2. $A_l, A_l+1, ... , A_r$ 의 합 구하기

이 두 가지 연산을 O(NlogN) 에 수행하려면 가장 먼저 떠오르는 것은 lazy propagation 이다. 하지만 이를 펜윅트리로 풀어보려 한다.

먼저 위의 두 가지 연산은 아래 두 연산을 수행함으로써 충분하다.

3. $A_x, A_x+1, ... , A_n$ 에 각각 k만큼 덧셈 = 함수 $f(x, k)$

4. $A_1, A_x+1, ... , A_x$ 의 합 구하기 = 함수 $g(x)$

라고 했을 때

$f(l,k)$ 와  $f(r+1,-k)$ 를 수행하면 1번 연산이고

$g(r) - g(l-1)$ 값이 2번 연산이기 때문이다.

함수 $f$, $g$ 는 펜윅으로 계산이 될 거 같지만 어떻게 펜윅트리로 짜야하는지는 막막하다.

 

$f(a,k)$연산 이후에 $g(b)$이 얼마나 변하는 지 생각해보자.

$\Delta g(b) = (b-a+1) \times k =  k \times b + (-a+1)k$

위의 식을 b에 대한 일차식으로 바라보자.

(참고로 $f(r+1, -k)$ 을 수행하면 $\Delta g(b)= (b-r) \times (-k) = -k \times b + rk$ 이다.)

 

즉. 일차항의 계수인 $k$에 대한 펜윅트리 하나(1번, one)와

상수항인 $(-a+1)k$에 대한 펜윅트리 하나(2번, zero)를 만들어 놓고

$f(a,k)$ 연산을 할 때마다 구간 $[a,n]$을 업데이트 해주면 $(1번 값) \times b + (2번 값)$ 로 $g(b)$ 를 구할 수 있다.

 

코드로 보는 것이 더 편한 경우가 많으니 이해가 안된다면 나머지는 코드를 보자.

 

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define MOD 1000000007 
#define INF 987654321 

int n, m, l;
ll one[4000010];
ll zero[4000010];

void update(ll pos, ll o, ll z){
	while(pos <= n){
		one[pos] += o;
		zero[pos] += z;
		pos += (pos & -pos);
	}
}

void rangeupdate(ll l, ll r, ll k){
	update(l, k, (-l + 1) * k);
	update(r + 1, -k, r * k);
}

ll query(ll pos){
	ll o = 0;
	ll z = 0;
	ll fix = pos;
	while(pos > 0){
		o += one[pos];
		z += zero[pos];
		pos -= (pos & -pos);
	}
	return o * fix + z;
}

int main(){
	scanf("%d %d %d", &n, &m, &l);
	for(int i = 1; i <= n; i++){
		ll num;
		scanf("%d", &num);
		rangeupdate(i, i, num);
	}
	for(int i = 0; i < m + l; i++){
		ll a, b, c, d;
		scanf("%lld %lld %lld", &a, &b, &c);
		if(a == 1){
			scanf("%lld", &d);
			rangeupdate(b, c, d);
		}else{
			printf("%lld\n", query(c) - query(b-1));
		}
	}
	return 0;
}

 

 

재밌게도 

www.acmicpc.net/problem/12844

12844번: XOR

이 문제도 구간 xor 연산이 펜윅트리로 계산되기 때문에 lazy propagation 대신 펜윅트리로 해결 가능하다.

위에서는 각 원소에 $k$만큼 더하는 것이었는데 이번에는 각 원소에  $k$만큼 xor 연산을 하는 것이 달라졌다.

하지만 마찬가지로 함수 $g$의 변화량을 체크해서 풀어줄 수 있다. 자세한 설명은 코드로 대체한다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define MOD 1000000007 
#define INF 987654321 

int n, m;
int one[500001];
int zero[500001];

void update(int pos, int o, int z){
	while(pos <= n){
		one[pos] ^= o;
		zero[pos] ^= z;
		pos += (pos & -pos);
	}
}

void rangeupdate(int l, int r, int k){
	update(l, k, ((l-1)%2)*k);
	update(r + 1, k, (r%2)*k);
}

int query(int pos){
	int fix = pos;
	int o = 0;
	int z = 0;
	while(pos > 0){
		o ^= one[pos];
		z ^= zero[pos];
		pos -= (pos & -pos);
	}
	return (o*(fix%2)) ^ z;
}

int main(){
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		int tmp;
		scanf("%d", &tmp);
		rangeupdate(i +1, i +1, tmp);
	}
	scanf("%d", &m);
	for(int i = 0; i < m; i++){
		int a, b, c, d;
		scanf("%d %d %d", &a, &b, &c);
		if(a == 1){
			scanf("%d", &d);
			rangeupdate(b+1, c+1, d);
		}else{
			printf("%d\n",query(c+1) ^ query(b));
		}
	}
	return 0;
}