10999 구간 합 구하기 2 with Lazy Propagation

 

2차원 세그먼트 트리까지 공부를 하고 Lazy Propagation을 배우게 되었다. 직역하면 게으른 전파라는 소리이다. 

이것을 쓰는 이유는 구간 전체를 변경할 때 빠르게 구하기 위해서이다. 기존 세그먼트 트리에서 Update를 할 때 한 점을 갱신한다. 왼쪽 오른쪽 구간을 나누고 구간 안에 속해있으면 탐색을 안 하기 위해서 세그먼트 트리를 쓰는 것인데 구간 전체를 변경하게 된다면 결국 각각의 점을 들어가서 변경을 해야 한다. 이러한 비효율적인 일을 막기 위해서 변경은 나중에 방문을 할 경우 한 번에 하고 변경되는 값을 따른 배열에 모아놓는 것이다.

 

자세한 구현법은 코드와 함께 정리하겠다.

 

1. 먼저 세그먼트 트리와 똑같은 크기의 Lazy 배열을 만든다. 

 

2. 그리고 기본적인 세그먼트 트리와 똑같이 구현을 한다.

void update(int idx, int l, int r, int i, int j, int val) {
	if (r < i || j < l) return;
	if (i <= l && r <= j) {
		seg[idx] += (r * 1LL - l + 1) * val;
		return;
	}
	int mid = (l + r) >> 1;
	update(idx << 1, l, mid, i, j, val);
	update(idx << 1 | 1, mid + 1, r, i, j, val);
	seg[idx] = seg[idx << 1] + seg[idx << 1 | 1];
}

점 갱신이 아니라 구간 갱신이므로 구간 내 범위이면 갱신을 해준다.

 

3. 구간 합이므로 아래 점들을 하나하나 방문하지않고 구간의 개수만큼 값을 곱하여 변경을 한다. 하지만 여기서 끝나게 되면 왼쪽 자식들과 오른쪽 자식들은 값이 변경이 되지 않는다.

따라서 왼쪽과 아래 Lazy 배열에 값을 더해준다.

if (i <= l && r <= j) {
	seg[idx] += (r * 1LL - l + 1) * val;
	if (l != r) {
		lazy[idx << 1] += val;
		lazy[idx << 1 | 1] += val;
	}
	return;
}

 

4. lazy 배열로 변경을 바로 하지 않고 넘어갔으므로 다음에 노드를 방문할 때 lazy 배열에 남아있는 값을 경신해줘야 한다.

void update_lazy(int idx, int l, int r) {
	if (lazy[idx] != 0) {
		seg[idx] += (r * 1LL - l + 1) * lazy[idx];
		if (l != r) {
			lazy[idx << 1] += lazy[idx];
			lazy[idx << 1 | 1] += lazy[idx];
		}
		lazy[idx] = 0;
	}
}

이렇게 쌓인 Lazy 배열을 방문할 때 한 번에 갱신해주는 것이다. 

이것을 정리해주면 다음 코드가 나오게 된다.

void update(int idx, int l, int r, int i, int j, int val) {
	update_lazy(idx, l, r);
	if (r < i || j < l) return;
	if (i <= l && r <= j) {
		seg[idx] += (r * 1LL - l + 1) * val;
		if (l != r) {
			lazy[idx << 1] += val;
			lazy[idx << 1 | 1] += val;
		}
		return;
	}
	int mid = (l + r) >> 1;
	update(idx << 1, l, mid, i, j, val);
	update(idx << 1 | 1, mid + 1, r, i, j, val);
	seg[idx] = seg[idx << 1] + seg[idx << 1 | 1];
}

일단 방문을 하면 lazy 배열을 체크해주고 수행해주면 된다.

 

아래는 문제의 전체 코드이다.

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define fu(i,a,j) for(int i=a;i<j;i++)
#define fd(i,a,j) for(int i=a;i>=j;i--)
#define SYNC ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define MOD 998244353
#define MOD2 1000000021
#define INF 1e9
#define N 1000001
using namespace std;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); };
int n, m, k, t;
int dr[] = { 0,0,1,-1, -1,1,1,-1 };
int dc[] = { -1,1,0,0, 1,1,-1,-1 };

int h = 1;
vll seg;
vll lazy;
ll a[N];
void init(int idx, int l, int r) {
	if (l != r) {
		init(idx << 1, l, (l + r) >> 1);
		init(idx << 1 | 1, ((l + r) >> 1) + 1, r);
		seg[idx] = seg[idx << 1] + seg[idx << 1 | 1];
	}
	else {
		seg[idx] = a[l];
	}
}

void update_lazy(int idx, int l, int r) {
	if (lazy[idx] != 0) {
		seg[idx] += (r * 1LL - l + 1) * lazy[idx];
		if (l != r) {
			lazy[idx << 1] += lazy[idx];
			lazy[idx << 1 | 1] += lazy[idx];
		}
		lazy[idx] = 0;
	}
}

void update(int idx, int l, int r, int i, int j, int val) {
	update_lazy(idx, l, r);
	if (r < i || j < l) return;
	if (i <= l && r <= j) {
		seg[idx] += (r * 1LL - l + 1) * val;
		if (l != r) {
			lazy[idx << 1] += val;
			lazy[idx << 1 | 1] += val;
		}
		return;
	}
	int mid = (l + r) >> 1;
	update(idx << 1, l, mid, i, j, val);
	update(idx << 1 | 1, mid + 1, r, i, j, val);
	seg[idx] = seg[idx << 1] + seg[idx << 1 | 1];
}

ll getval(int idx, int l, int r, int i, int j) {
	update_lazy(idx, l, r);
	if (r < i || j < l) return 0;
	if (i <= l && r <= j) {
		return seg[idx];
	}
	int mid = (l + r) >> 1;
	return getval(idx << 1, l, mid, i, j) + getval(idx << 1 | 1, mid + 1, r, i, j);
}

int main() {
	SYNC;
	cin >> n >> m >> k;
	while (h < n) h <<= 1;
	seg.resize(h << 1);
	lazy.resize(h << 1);
	fu(i, 1, n + 1) {
		cin >> a[i];
	}
	init(1, 1, n);
	fu(i, 0, m + k) {
		int a, b, c, d;
		cin >> a;
		if (a == 1) {
			cin >> b >> c >> d;
			update(1, 1, n, b, c, d);
		}
		else {
			cin >> b >> c;
			cout << getval(1, 1, n, b, c) << '\n';
		}
	}
	return 0;
}