对应的水题是poj3468
今天实验室的大牛说了线段树的区间修改值在求和,(其实自己线段树还没懂太多了)觉得他们好强啊,有一道这个的模板题,在这里贴一下模板代码,自己忘了就可以再来看看.
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long int
using namespace std;
const int MAXN = 2e5+1e3;
struct Node{
int minv, addv, maxv, sumv;
}tree[MAXN<<2];
ll a[MAXN], n;
//建树 //1 0 n-1
void build(int id, int tl, int tr) {
tree[id].addv = 0;
if(tl==tr){
tree[id].minv = a[tl];
tree[id].maxv = a[tl];
tree[id].sumv = a[tl];
}
else {
int tm = tl+tr>>1;
build(id<<1, tl, tm);//递归建树//左儿子
build(id<<1|1, tm+1, tr);//右儿子 //*2+1的意思.
tree[id].minv = min(tree[id<<1].minv, tree[id<<1|1].minv);
tree[id].maxv = max(tree[id<<1].maxv, tree[id<<1|1].maxv);
tree[id].sumv = tree[id<<1].sumv+tree[id<<1|1].sumv;
}
}
//放下懒人标记
void pushdown(int id,int tl, int tr) {
int& x = tree[id].addv;//用的别名
int tm = tl+tr>>1;
tree[id<<1].minv += x;
tree[id<<1].maxv += x;
tree[id<<1].addv += x;
tree[id<<1].sumv += x*(tm-tl+1);
tree[id<<1|1].minv += x;
tree[id<<1|1].maxv += x;
tree[id<<1|1].addv += x;
tree[id<<1|1].sumv += x*(tr-tm);
x = 0;//如果x改变,则赋给它值的也会改变
}
//增加区间和
void add(int id, int tl, int tr, int ql, int qr, int v) {
if(ql<=tl&&tr<=qr) {
tree[id].addv += v;
tree[id].minv += v;
tree[id].maxv += v;
tree[id].sumv += v*(tr-tl+1);
return;
}
if(tl<tr) pushdown(id,tl,tr);
int tm = tl+tr>>1;
if(tl<=qr&&tm>=ql)
add(id<<1, tl, tm, ql, qr, v);
if(tr>=ql&&tm+1<=qr)
add(id<<1|1, tm+1, tr, ql, qr, v);
if(tl<tr) {
tree[id].minv = min(tree[id<<1].minv, tree[id<<1|1].minv);
tree[id].maxv = max(tree[id<<1].maxv, tree[id<<1|1].maxv);
tree[id].sumv = tree[id<<1].sumv+tree[id<<1|1].sumv;
}
}
//求区间最小值
int query(int id, int tl, int tr, int ql, int qr) {
if(ql<=tl&&tr<=qr) {
return tree[id].minv;
}
if(tl<tr) pushdown(id,tl,tr);
int tm = tl+tr>>1;
int ret = (1<<31)-1;
if(tl<=qr&&tm>=ql)
ret = query(id<<1, tl, tm, ql, qr);
if(tr>=ql&&tm+1<=qr)
ret = min(ret, query(id<<1|1, tm+1, tr, ql, qr));
return ret;
}
//求区间最大值
int queryX(int id, int tl, int tr, int ql, int qr) {
if(ql<=tl&&tr<=qr) {
return tree[id].maxv;
}
if(tl<tr) pushdown(id,tl,tr);
int tm = tl+tr>>1;
int ret = 0;
if(tl<=qr&&tm>=ql)
ret = queryX(id<<1, tl, tm, ql, qr);
if(tr>=ql&&tm+1<=qr)
ret = max(ret, queryX(id<<1|1, tm+1, tr, ql, qr));
return ret;
}
//求区间和
int querysum(int id, int tl, int tr, int ql, int qr)
{
if(ql<=tl&&tr<=qr)
{
return tree[id].sumv;
}
if(tl<tr) pushdown(id, tl, tr);
int tm = tl+tr>>1;
int ret = 0;
if(tl<=qr&&tm>=ql)
ret = querysum(id<<1, tl, tm, ql, qr);
if(tr>=ql&&tm+1<=qr)
ret += querysum(id<<1|1, tm+1, tr, ql, qr);
return ret;
}
int main(){
int Q;
char str[5];
scanf("%d %d", &n , &Q);
for(int i=0; i<n; ++i){
scanf("%d", a+i);
}
int l,r,k;
build(1, 0, n-1);
for(int i=0;i<Q;i++){
scanf("%s",str);
if(str[0]=='Q'){
scanf("%d %d",&l,&r);
printf("%d\n",querysum(1,0,n-1,l-1,r-1));//因为建树是从0开始的,而询问是加了一的,所以要减一.
}
else if(str[0]=='C'){
scanf("%d%d%d",&l,&r,&k);
add(1,0,n-1,l-1,r-1,k);//别忘减一.
}
}
}
网友评论