題目鏈接：[點擊打開鏈接](http://poj.org/problem?id=3468) 題意：區間加減，區間求和。 該題是線段樹區間增減和區間求和的模板題。 和區間修改值一樣， 在每個結點上維護一個之前加減的值， 那么每次經過一個結點時， 當前結點一定已經擁有所有結點信息。 每次遞歸前下傳結點信息，這就是所謂的懶惰標記。? 細節參見代碼： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int INF = 1000000000; const int maxn = 100000 + 10; int T,n,l,r,q,v; ll sum[maxn<<2],addv[maxn<<2]; char s[10]; void push_up(int o) { sum[o] = sum[o<<1] + sum[o<<1|1]; } void build(int l, int r, int o) { int m = (l + r) >> 1; addv[o] = 0; if(l == r) { scanf("%lld",&sum[o]); return ; } build(l, m, o<<1); build(m+1, r, o<<1|1); push_up(o); } void pushdown(int o, int l, int r) { if(addv[o]) { int m = (l + r) >> 1; addv[o<<1] += addv[o]; addv[o<<1|1] += addv[o]; sum[o<<1] += (ll)(m - l + 1) * addv[o]; sum[o<<1|1] += (ll)(r - m) * addv[o]; addv[o] = 0; } } void update(int L, int R, int v, int l, int r, int o) { int m = (l + r) >> 1; if(L <= l && r <= R) { addv[o] += v; sum[o] += (ll)v * (r - l + 1); return ; } pushdown(o, l, r); if(L <= m) update(L, R, v, l, m, o<<1); if(m < R) update(L, R, v, m+1, r, o<<1|1); push_up(o); } ll query(int L, int R, int l, int r, int o) { int m = (l + r) >> 1; if(L <= l && r <= R) { return sum[o]; //當前結點一定已經擁有所有的標記 } ll ans = 0; pushdown(o, l, r); if(L <= m) ans += query(L, R, l, m, o<<1); if(m < R) ans += query(L, R, m+1, r, o<<1|1); push_up(o); return ans; } int main() { while(~scanf("%d%d",&n,&q)) { build(1, n, 1); while(q--) { scanf("%s%d%d",s,&l,&r); if(s[0] == 'Q') { printf("%lld\n",query(l, r, 1, n, 1)); } else { scanf("%d",&v); update(l, r, v, 1, n, 1); } } } return 0; } ~~~