【範例】區間修改 + 懶標記 (Lazy Tag)
【題目敘述】https://vjudge.net/problem/POJ-3468
【解題想法】線段樹 (Segment Tree)，區間修改 + 懶標記 (Lazy Tag)
- Lazy Tag：每次修改區間資料時，只修改「當前區間」的值。「子區間」的值暫時不更新，但會在當前區間的lazy tag留下記號。等到下次query或update需要時，再依照父節點的lazy tag來更新子節點的值，然後把lazy tag傳遞給子節點，同時移除父節點的lazy tag。
- update( ):
- 若區間[l, r]完全被[ul, ur]包覆時，更新total[x]，同時更新lazy[x]。
- 否則，先進行push( )。接著處理左右兒子的lazy tag，再update左右兒子。
- 最後記得pull( )。
- query( ):
- 若需要讀取左右兒子的值，要先進行push( )，確保資料正確。
- 不需要pull( )。
#include <iostream>
using namespace std;
int n, q, a, b, c;
char C;
long long total[100005 << 2], lazy[100005 << 2];
void pull(int x){
total[x] = total[x<<1] + total[x<<1|1];
}
void push(int x, int l, int r){
if (lazy[x] == 0) return;
int mid = (l + r) >> 1;
lazy[x<<1] += lazy[x];
lazy[x<<1|1] += lazy[x];
total[x<<1] += lazy[x] * (mid - l + 1);
total[x<<1|1] += lazy[x] * (r - mid);
lazy[x] = 0;
}
void build(int x, int l, int r){
if (l == r){
cin >> total[x];
return;
}
int mid = (l + r) >> 1;
build(x<<1, l, mid);
build(x<<1|1, mid+1, r);
pull(x);
}
void update(int x, int l, int r, int ul, int ur){
//[ul, ur]: 更新區間
if (ul <= l && r <= ur){
lazy[x] += c;
total[x] += c * (r-l+1);
return;
}
push(x, l, r);
int mid = (l + r) >> 1;
if (ul <= mid) update(x<<1, l, mid, ul, ur);
if (mid < ur) update(x<<1|1, mid+1, r, ul, ur);
pull(x);
}
long long query(int x, int l, int r, int ql, int qr){
//[ql, qr]: 查詢區間
if (ql <= l && r <= qr){
return total[x];
}
long long ans = 0;
int mid = (l + r) >> 1;
push(x, l, r);
if (ql <= mid) ans += query(x<<1, l, mid, ql, qr);
if (mid < qr) ans += query(x<<1|1, mid+1, r, ql, qr);
return ans;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
while (cin >> n >> q){
build(1, 1, n);
for (int i = 0; i < q; i++){
cin >> C;
if (C == 'C'){
cin >> a >> b >> c;
update(1, 1, n, a, b);
}else{
cin >> a >> b;
cout << query(1, 1, n, a, b) << "\n";
}
}
cout << "\n";
}
}