上网搜吧,有这些题解的
by moye到碗里来 @ 2017-08-22 21:24:47
建议看模板线段树1题解,有很详细的版本
by Broadway @ 2017-08-22 21:25:45
谢谢
by zyywzw @ 2017-08-22 21:33:59
naive
by zcysky @ 2017-08-23 00:11:42
```cpp
@[kmzx张宇阳wzw](/space/show?uid=28906)
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=300010;
typedef long long ll;
struct SegTreeNode{ll Val=0,AddMark=0;}SegTree[maxn];
void Build(int o,int l,int r,ll a[]){
if(l==r){SegTree[o].Val=a[l];return;}
int mid=(l+r)>>1;
Build(o*2,l,mid,a);
Build(o*2+1,mid+1,r,a);
SegTree[o].Val=SegTree[o*2].Val+SegTree[o*2+1].Val;
}
void Update(int o,int l,int r,int ul,int ur,ll AddVal){
if(l>ur||r<ul)return;
if(l>=ul&&r<=ur){
SegTree[o].AddMark+=AddVal;
SegTree[o].Val+=AddVal*(r-l+1);
return;
}
int mid=(l+r)>>1;
if(SegTree[o].AddMark!=0){
SegTree[o*2].AddMark+=SegTree[o].AddMark;
SegTree[o*2+1].AddMark+=SegTree[o].AddMark;
SegTree[o*2].Val+=SegTree[o].AddMark*(mid-l+1);
SegTree[o*2+1].Val+=SegTree[o].AddMark*(r-mid);
SegTree[o].AddMark=0;
}
Update(o*2,l,mid,ul,ur,AddVal);
Update(o*2+1,mid+1,r,ul,ur,AddVal);
SegTree[o].Val=SegTree[o*2].Val+SegTree[o*2+1].Val;
}
ll Query(int o,int l,int r,int ql,int qr){
if(ql>r||qr<l)return 0;
if(ql<=l&&qr>=r)return SegTree[o].Val;
int mid=(l+r)>>1;
if(SegTree[o].AddMark!=0){
SegTree[o*2].AddMark+=SegTree[o].AddMark;
SegTree[o*2+1].AddMark+=SegTree[o].AddMark;
SegTree[o*2].Val+=SegTree[o].AddMark*(mid-l+1);
SegTree[o*2+1].Val+=SegTree[o].AddMark*(r-mid);
SegTree[o].AddMark=0;
}
return Query(o*2,l,mid,ql,qr)+Query(o*2+1,mid+1,r,ql,qr);
}
int n,m,op,q1,q2;ll q3,a[maxn];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
Build(1,1,n,a);
while(m--){
scanf("%d",&op);
if(op==1){
scanf("%d%d%lld",&q1,&q2,&q3);
Update(1,1,n,q1,q2,q3);
}
else{
scanf("%d%d",&q1,&q2);
printf("%lld\n",Query(1,1,n,q1,q2));
}
}
return 0;
}
```
by hsfzLZH1 @ 2017-08-23 20:44:41
@[hsfzLZH1](/space/show?uid=43486) 你不写pushdown 啊,这不是一个好习惯
by cszmc2004 @ 2017-08-25 09:34:55
@[lingjiyidong21](/space/show?uid=35490) %%%
by hsfzLZH1 @ 2017-08-25 10:23:32
@[hsfzLZH1](/space/show?uid=43486) %%%
by cszmc2004 @ 2017-08-25 14:23:14
```cpp
#include<stdio.h>
#include<string>
#include<string.h>
#include<algorithm>
using namespace std;
long long sumv[1<<20+1],arr[1<<20+1],addv[1<<20+1];
#define inf 2000000000
void pushdown(int o,int l,int r){
if(addv[o]!=0){
int mid=(l+r)>>1;
addv[o*2]+=addv[o];
addv[o*2+1]+=addv[o];
sumv[o*2]+=(mid-l+1)*addv[o];
sumv[o*2+1]+=(r-mid)*addv[o];
addv[o]=0;
}
}
void build(int l,int r,int o){
addv[o]=0;
if(l==r){sumv[o]=arr[l];return;}
int mid=(l+r)>>1;
build(l,mid,o*2);
build(mid+1,r,o*2+1);
sumv[o]=sumv[o<<1]+sumv[(o<<1)+1];
}
long long query(int l,int r,int o,int y1,int y2){
if(y1>r||y2<l)return 0;
if(y1<=l&&y2>=r)return sumv[o];
pushdown(o,l,r);
int mid=(l+r)>>1;
return query(l,mid,o*2,y1,y2)+query(mid+1,r,o*2+1,y1,y2);
}
void update(int l,int r,int o,int y1,int y2,int val){
if(y1>r||y2<l)return;
if(y1<=l&&y2>=r){
sumv[o]+=val*(r-l+1);addv[o]+=val;
return;
}
pushdown(o,l,r);
int mid=(l+r)>>1;
update(l,mid,o<<1,y1,y2,val);update(mid+1,r,(o<<1)+1,y1,y2,val);
sumv[o]=sumv[o<<1]+sumv[(o<<1)+1];
}
int main(){
//freopen("in.txt","r",stdin);
//freopen("myout.txt","w",stdout);
int a,b,c,d,e,f;
scanf("%d",&a);
scanf("%d",&b);
for(int i=1;i<=a;i++)scanf("%lld",&arr[i]);
build(1,(1<<17),1);
for(int i=0;i<b;i++){
scanf("%d",&c);
if(c==1){
scanf("%d %d %d",&d,&e,&f);
update(1,(1<<17),1,d,e,f);
}
if(c==2){
scanf("%d %d",&d,&e);
printf("%lld\n",query(1,(1<<17),1,d,e));
}
}
}
```
by cszmc2004 @ 2017-09-21 21:28:43