문제

어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째부터 4번째 수에 6을 더하면 1, 2, 9, 10, 5가 되고, 여기서 2번째부터 5번째까지 합을 구하라고 한다면 26을 출력하면 되는 것이다. 그리고 그 상태에서 1번째부터 3번째 수에 2를 빼고 2번째부터 5번째까지 합을 구하라고 한다면 22가 될 것이다.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c 또는 a, b, c, d가 주어지는데, a가 1인 경우 b번째 수부터 c번째 수에 d를 더하고, a가 2인 경우에는 b번째 수부터 c번째 수의 합을 구하여 출력하면 된다.

입력으로 주어지는 모든 수는 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.

출력

첫째 줄부터 K줄에 걸쳐 구한 구간의 합을 출력한다. 단, 정답은 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.

구간 업데이트가 발생할때 갱신을 느리게 갱신해야합니다.

느리게 갱신되는 세그먼트 트리 (Segment Tree with Lazy Propagation)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll d[1000001];
ll tree[4000004];
ll lazy[4000001];
ll init(ll s, ll e, ll n) {
	if (s == e)
		return tree[n] = d[s];
	ll m = (s + e) / 2;
	return tree[n] = init(s, m, n * 2) + init(m + 1, e, n * 2 + 1);
}
void lazy_update(ll l, ll r, ll n) {
	if (lazy[n]) {
		tree[n] += (r - l + 1) * lazy[n];
		if (l != r) {
			lazy[2 * n] += lazy[n];
			lazy[2 * n + 1] += lazy[n];
		}
		lazy[n] = 0;
	}
}
ll query(ll l, ll r, ll n, ll f,ll t) {
	lazy_update(l, r, n);
	if (r < f || t < l)return 0;

	if (f <= l && r <= t) {
		return tree[n];
	}
	ll mid = (l + r) / 2;
	return query(l, mid, n * 2, f, t) + query(mid + 1, r, n * 2 + 1, f, t);
}

ll update(ll l,ll r,ll n,ll f,ll t,ll v){
	lazy_update(l, r, n);
	if (r < f || t < l)return tree[n]; //범위 밖

	if (f <= l && r <= t) {//범위 내
		if (l != r) {
			lazy[2 * n] += v;
			lazy[2 * n + 1] += v;
		}
		return tree[n] += (r - l + 1) * v;
	}

	//걸침
	ll mid = (l + r) / 2;
	return tree[n]=update(l, mid, n * 2, f, t, v)+update(mid + 1, r, n * 2 + 1, f, t, v);
}
int main() {
	cin.tie(NULL); ios_base::sync_with_stdio;
	ll n, m, x, k;
	cin >> n >> m >> k;
	for (ll i = 1; i <= n; i++) {
		cin >> x;
		d[i] = x;
	}
	ll a, b, c, dif;
	init(1, n, 1);
	for (ll i = 0; i < m + k; i++) {

		cin >> a;
		if (a == 1) {
			cin >> b >> c >> dif;
			update(1,n,1,b,c,dif);
		}
		else {
			cin >> b >> c;
			cout << query(1,n,1,b,c) << "\n";
		}

	}
}

구간 업데이트가 발생할 때 케이스 3개가 있습니다.

1. 범위 내일때

범위 내일때, n번째 정점을 바로 업데이트합니다. (l-r+1)*v 를 더함. 그리고, 자식노드에게 lazy를 부여합니다

2. 범위 외일때

업데이트가 필요 없습니다.

3. 범위 겹칠때

좌우로 나누어 업데이트를 진행합니다.

만약 현재 방문한 노드가 lazy가 존재하면 아래 노드로 pushdown을 진행해야합니다.

위 코드에서는 lazy_update 함수가 pushdown을 진행합니다. 그리고 이 pushdown 은 update와 query 둘 모두에서 진행해야합니다.

lazy_update함수는 만약 방문한 정점이 lazy값이 존재하는 경우, 이를 업데이트하고 자식노드에게 lazy값을 전가하는 역할을 합니다.