POJ 3468 A Simple Problem with Integers（线段树|区间加减&&区间求和）
最后更新于：2022-04-01 15:53:18
题目链接：[点击打开链接](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;
}
~~~