lazy propagation 없이 구간 합 + 구간 업데이트 쿼리 처리하기

사실 별건 아닌데, 내가 애초에 세그 트리를 비재귀로 구현하다 보니가, 레이지가 너무 안 익숙해서 정리한다.

레이지는 대부분 재귀로 구현하고 (비재귀 방식도 있다고는 한다...) 그렇다 보니까 구현도 길어지고 그러는데, 나중에 scpc같은 곳에서 팀노트 없을 때 빠르게 구현해 낼 자신이 없을 때 가끔 써먹어야 겠다...

 

아 근데 (금광 + 레이지) 세그 비재귀로 짤때는 잘 써먹고 있다.

 

시간복잡도는 O(nloglogn)인데, 다음과 같은 방식을 이용한다.

 

1. 업데이트: 구간 [L,R]에 c만큼 더하기. 

세그트리 base이기 때문에 최대 특정 길이의 구간은 logN개의 노드로 분할된다.

현재 노드를 x라 하자.

이 노드에 다음과 같은 작업을 할 것이다. 이 노드의 자식 노드들을 업데이트 하지는 않는다.

그저 현재 노드의 A[x]값에 c를 더하자.이 A값의 뜻은, 현재 노드에 전체 구간에 더해진 양을 의미한다.

업데이트 할 것 들은 x라는 노드의 부모와 조상 노드들이다.

맨 위의 루트노드까지 부모를 타고 올라가며 c*(node x의 크기)값씩 A말고 구간 전체에 더해주자.

 

2. 쿼리: 구간 [L,R]의 합 구하기.

마찬가지로 logN개의 노드로 분할한다.

그리고 각 노드마다 다음과 같은 작업을 한다.

ret에 현재 노드의 값을 더한다. 그리고 그 노드로부터 루트 노드 까지 부모를 타고 올라가면서 A값들의 합을 저장한다.

그리고 마지막으로, (A값들의 합)*(node x의 크기)를 ret에 더한다.

 

이런식으로 하면 log가 하나 더 붙고 문제를 풀 수 있다.

그런데 비재귀 vs 재귀라 시간차이가 별 안나기도 한다.

오히려 이게 더 빨랐다... 별 차이 없긴 수치긴 하지만

코드는 아래와 같다.

#include<bits/stdc++.h>
//#define double long double
//T.erase(unique(T.begin(),T.end()),T.end());
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ = 1e6 + 100, inf = (ll)1e9 * (ll)1e9 + 7, mod = 1e9+7, sqrtN = 320;
ll dy[4] = { -1,0,1,0 }, dx[4] = { 0,1,0,-1 };
ll n, m, k, tc = 1, a, b, c, d, sum, x, y, z, base, ans, q;
ll gcd(ll x, ll y) {
	if (!y)return x;
	return gcd(y, x % y);
}
ll tree[n_ * 4], A[n_ * 4];
void u(ll x, ll val, ll sz) {
	A[x] += val;
	x /= 2;
	while (x) {
		tree[x] += val * sz;
		x /= 2;
	}
}
void update(ll l, ll r, ll val) {
	l += base, r += base;
	ll sz = 1;
	while (l <= r) {	
		if (l % 2)u(l++, val, sz); 
		if (!(r % 2))u(r--, val, sz);
		l /= 2, r /= 2;
		sz *= 2;
	}
}
ll get(ll x,ll sz) {
	ll ret = tree[x];
	while (x) {
		ret += A[x] * sz;
		x /= 2;
	}
	return ret;
}
ll f(ll l, ll r) {
	l += base, r += base;
	ll ret = 0, sz = 1;
	while (l <= r) {
		if (l % 2)ret += get(l++,sz);
		if (!(r % 2))ret += get(r--,sz);
		l /= 2, r /= 2;
		sz *= 2;
	}
	return ret;
}
void solve() {
	cin >> n >> m >> k;
	for (base = 1; base < n; base *= 2);
	for (int i = 0; i < n; i++)cin >> tree[base + i];
	for (int i = base - 1; i; i--)tree[i] = tree[i * 2] + tree[i * 2 + 1];
	for (int i = 0; i < m + k; i++) {
		cin >> a;
		if (a == 1) {
			cin >> b >> c >> d;
			update(b - 1, c - 1, d);
		}
		else {
			cin >> b >> c;
			cout << f(b - 1, c - 1) << '\n';
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	//cin >> tc;
	while (tc--)solve();
}