线段树模板（单标记）

P3372【模板】线段树 1

1.将某区间每一个数加上x

2.求出某区间每一个数的和

#include<bits/stdc++.h> using namespace std; #define MAX 100005 #define ll long long #define inf 0x3f3f3f int num[MAX]; struct node{ ll val; ll add; }segtree[(MAX<<2)+5]; void build(int root,int nl,int nr){ segtree[root].add=0; if(nl==nr){ segtree[root].val=num[nl]; return ; } int mid=nl+nr>>1; build(root<<1,nl,mid); build(root<<1|1,mid+1,nr); segtree[root].val=segtree[root<<1].val+segtree[root<<1|1].val;//?update??? } void pushdown(int root,int nl,int nr){ if(segtree[root].add){ int mid = nr+nl>>1; segtree[root<<1].val+=(segtree[root].add)*(mid-nl+1); segtree[root<<1|1].val+=segtree[root].add*(nr-mid); segtree[root<<1].add+=segtree[root].add; segtree[root<<1|1].add+=segtree[root].add; segtree[root].add=0; } } ll query(int root,int nl,int nr,int ql,int qr){ if(nl>qr||nr<ql){ return 0; } if(nl>=ql&&nr<=qr){ return segtree[root].val; } pushdown(root,nl,nr); int mid=nl+nr>>1; return query(root<<1,nl,mid,ql,qr)+query(root<<1|1,mid+1,nr,ql,qr); } void update(int root,int nl,int nr,int ql,int qr,int add){ if(nl>qr||nr<ql){ return ; } if(nl>=ql&&nr<=qr){ segtree[root].val+=(nr-nl+1)*add; segtree[root].add+=add; return ; } if(nl==nr){ segtree[root].val+=add; return ; } pushdown(root,nl,nr); int mid=nl+nr>>1; update(root<<1,nl,mid,ql,qr,add); update(root<<1|1,mid+1,nr,ql,qr,add); segtree[root].val=segtree[root<<1].val+segtree[root<<1|1].val;//?build??? } int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&num[i]); } build(1,1,n); for(int i=1;i<=m;i++){ int a; scanf("%d",&a); if(a==1){ int b,c,d; scanf("%d%d%d",&b,&c,&d); update(1,1,n,b,c,d); } else { int b,c; scanf("%d%d",&b,&c); printf("%lld\n",query(1,1,n,b,c)); } } return 0; }

HDU-1166

#include<bits/stdc++.h> using namespace std; #define MAX 50005 int a[MAX]; struct node{ int val; int add; }segtree[(MAX<<2)+5]; void build(int root,int l,int r){ segtree[root].add=0; if(l==r){ segtree[root].val=a[l]; return ; } int mid=l+r>>1; build(root<<1,l,mid); build(root<<1|1,mid+1,r); segtree[root].val=segtree[root<<1].val+segtree[root<<1|1].val; } void pushdown(int root,int l,int r){ if(segtree[root].add){ int mid=l+r>>1; segtree[root<<1].val+=segtree[root].add*(mid+1-l); segtree[root<<1|1].val+=segtree[root].add*(r-mid); segtree[root<<1].add+=segtree[root].add; segtree[root<<1|1].add+=segtree[root].add; segtree[root].add=0; } } int query(int root,int l,int r,int ql,int qr){ if(l>qr||r<ql)return 0; if(l>=ql&&r<=qr)return segtree[root].val; pushdown(root,l,r); int mid=l+r>>1; return query(root<<1,l,mid,ql,qr)+query(root<<1|1,mid+1,r,ql,qr); } void update(int root,int l,int r,int ql,int qr,int delta){ if(l>qr||r<ql)return ; if(l>=ql&&r<=qr){ segtree[root].add=delta; segtree[root].val+=(r-l+1)*delta; return ; } if(l==r){ segtree[root].val+=delta; return ; } pushdown(root,l,r); int mid=l+r>>1; update(root<<1,l,mid,ql,qr,delta); update(root<<1|1,mid+1,r,ql,qr,delta); segtree[root].val=segtree[root<<1].val+segtree[root<<1|1].val; } int main(){ int pa; cin>>pa; int cnt=0; while(pa--){ int n; scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); printf("Case %d:\n",++cnt); build(1,1,n); char cmd[10]; while(scanf("%s",cmd),strcmp(cmd,"End")){ int a,b; scanf("%d%d",&a,&b); if(strcmp(cmd,"Query")==0)printf("%d\n",query(1,1,n,a,b)); else if(strcmp(cmd,"Add")==0)update(1,1,n,a,a,b); else if(strcmp(cmd,"Sub")==0)update(1,1,n,a,a,-b); } } return 0; }