정의
게으르게 전파하여 갱신하는 자료구조이다.
- 기존 세그먼트 트리는 갱신을 즉시 처리 했지만, Lazy를 이용하여 필요할 때 한꺼번에 처리한다.
- 특정 구간 [a, b]에 값 c를 동시에 연산할 때 사용된다
- 단순한 세그먼트 트리로 특정 구간의 길이 N을 연산 한다면 O(NlogN)가 걸리지만 O(logN)로 줄일 수 있다
예시 코드
세그먼트 트리 + Lazy propagation
- 세그먼트 트리는 완전 이진트리가 아닐 수 있음
- 그러므로 propagate 함수 안에 현재 노드가 자식인지를 확인하는 if(l != r)가 if(node < si)로 대체될 수 없음
// 백준 10999번 구간 합 구하기2
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int si = 1;
ll arr[1024*1024];
ll seg[1024*1024*2], lazy[1024*1024*2];
// 세그먼트 트리 초기화
long long init(int l, int r, int node){
if(l == r) return seg[node] = arr[l];
int mid = (l+r)/2;
return seg[node] = init(l, mid, node*2) + init(mid+1, r, node*2+1);
}
// Lazy Propagate
void propagate(int l, int r, int node){
if(lazy[node] == 0) return;
if(l != r){
lazy[node*2] += lazy[node];
lazy[node*2+1] += lazy[node];
}
seg[node] += lazy[node] * (r-l+1);
lazy[node] = 0;
}
// 구간의 값 변경
void update(int l, int r, int node, int st, int en, ll n) {
propagate(l, r, node);
if(en < l || r < st) return;
if(st <= l && r <= en) {
lazy[node] += n;
propagate(l, r, node);
return;
}
int mid = (l+r)/2;
update(l, mid ,node*2, st, en ,n);
update(mid+1, r, node*2+1, st, en, n);
seg[node] = seg[node*2] + seg[node*2+1];
}
// 구간의 합 구하기
ll sum(int l, int r, int node, int st, int en) {
propagate(l, r, node);
if(en < l || r < st) return 0;
if(st <= l && r <= en) return seg[node];
int mid = (l+r)/2;
return sum(l, mid, node*2, st, en) + sum(mid+1, r, node*2+1, st, en);
}
int main() {
ios::sync_with_stdio(0); cin.tie(NULL);
int n, m, k;
cin >> n >> m >> k;
while(si < n) si <<= 1;
for(int i = 0; i < n; i++)
cin >> arr[i];
init(0, n-1, 1);
ll a,b,c,d;
for(int i = 0; i < m+k; i++) {
cin >> a >> b >> c;
if(a == 1) {
cin >> d;
update(0, n-1, 1, b-1, c-1, d);
}
else
cout << sum(0, n-1, 1, b-1, c-1) << '\n';
}
return 0;
}같이 보면 좋을 글