本来不准备写备战 NOIP2017 系列了，无奈刷题刷爽了...
线段树#
维护区间修改查询的数据结构
第一行包含两个整数 N、M，分别表示该数列数字的个数和操作的总个数
第二行包含 N 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项的初始值
接下来 M 行每行包含 3 或 4 个整数，表示一个操作，具体如下：
- 格式：1 x y k 含义：将区间[x,y]内每个数加上 k
- 格式：2 x y 含义：输出区间[x,y]内每个数的和
#include<iostream>#include<cstdio>using std::cin;using std::cout;
typedef long long ll;
const int N=100000+10;
struct P{ int lc,rc; int l,r; ll sum,v;};
P tree[N*2];int tail=0;
int build_tree(int l,int r){ P &now=tree[tail++]; now.l=l;now.r=r; if(l+1<r){ int mid=l+(r-l)/2; now.lc=build_tree(l,mid); now.rc=build_tree(mid,r); } return &now-tree;}
void update(int p){ P &now=tree[p]; now.sum=now.v*(now.r-now.l); if(now.l+1<now.r)now.sum+=tree[now.lc].sum+tree[now.rc].sum;}
void push_down(int p){ P &now=tree[p]; tree[now.lc].v+=now.v; tree[now.rc].v+=now.v; now.v=0; update(now.lc); update(now.rc);}
void add(int l,int r,ll v,int p=0){ P &now=tree[p]; if(l==r)return; if(now.l>=r||now.r<=l)return; if(now.l>=l&&now.r<=r){ now.v+=v; }else{ push_down(p); add(l,r,v,now.lc); add(l,r,v,now.rc); } update(p);}
ll query(int l,int r,int p=0){ P &now=tree[p]; if(l>=r)return 0; if(now.l>=r||now.r<=l)return 0; if(now.l>=l&&now.r<=r)return now.sum; push_down(p); ll ret=query(l,r,now.lc)+query(l,r,now.rc); update(p); return ret;}
int main(){ std::ios::sync_with_stdio(false); int n,m; cin>>n>>m; build_tree(1,n+1); for(int i=1;i<=n;i++){ ll buf; cin>>buf;//scanf("%d",&buf); add(i,i+1,buf); } for(int k=0;k<m;k++){ int t,l,r; cin>>t>>l>>r; if(t==1){ ll v; cin>>v; add(l,r+1,v); }else{ cout<<query(l,r+1)<<'\n'; } //print(); } return 0;}zkw 线段树#
2013 年，《统计的力量》横空出世
zkw 线段树看起来很像树状数组（不知为什么...
zkw 线段树通过挖掘二叉树在数组中的特性，找到了一种可以快速定位叶子节点的方法，于是自顶向下的方法被抛弃，转而使用自底向上的方法
改段求点#
#include<cstdio>
const int N=500000+10;
int tree[N*3];int len=1;
void build(int n,int v=0){ while(len<n+2)len<<=1; for(int i=len+1;i<=len+n;i++)scanf("%d",&tree[i]);}
void add(int l,int r,int v){ for(l+=len-1,r+=len+1;l^r^1;l>>=1,r>>=1){ if(~l&1)tree[l+1]+=v; if(r&1)tree[r-1]+=v; }}
int query(int n,int res=0){ for(n+=len;n;n>>=1)res+=tree[n]; return res;}
int main(){ int n,m; scanf("%d%d",&n,&m); build(n); for(int i=0;i<m;i++){ int t,x; scanf("%d%d",&t,&x); if(t==1){ int y,v; scanf("%d%d",&y,&v); add(x,y,v); }else printf("%d\n",query(x)); } return 0;}改点求段#
#include<cstdio>
const int N=500000+10;
int tree[N*3];int len=1;
inline int Min(int a,int b){return a>b?b:a;}
void build(int n){ while(len<n+2)len<<=1; for(int i=len+1;i<=len+n;i++)scanf("%d",&tree[i]); for(int i=len;i>0;i--)tree[i]=tree[i<<1]+tree[i<<1^1];}
void add(int n,int v){ tree[n+len]+=v; for(n+=len;n>1;n>>=1) tree[n>>1]=tree[n]+tree[n^1];}
int query(int l,int r,int res=0){ for(l+=len-1,r+=len+1;l^r^1;l>>=1,r>>=1){ if(~l&1)res+=tree[l+1]; if(r&1)res+=tree[r-1]; } return res;}
int main(){ int n,m; scanf("%d%d",&n,&m); build(n); for(int i=0;i<m;i++){ int t,x,y; scanf("%d%d%d",&t,&x,&y); if(t==1)add(x,y); else printf("%d\n",query(x,y)); } return 0;}改段求段#
#include<cstdio>#include<iostream>using namespace std;
const int N=100000+10;
typedef long long ll;
ll val[N*4],sum[N*4];ll len[N*4];ll length=1;
long long read(){ char ch=getchar(); long long a=0,f=1; while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9') { a=a*10+ch-'0'; ch=getchar(); } return a*f;}
void build(int n){ while(length<n+2)length<<=1; for(int i=length+1;i<=length+n;i++){ val[i]=read(); sum[i]=val[i]; } for(int i=length;i>0;i--)sum[i]=sum[i<<1]+sum[i<<1^1]; for(int i=length+length-2;i>length;i--)len[i]=1; for(int i=length-1;i>0;i--)len[i]=len[i<<1]+len[i<<1^1];}
void add(ll l,ll r,ll v){ for(l+=length-1,r+=length+1;l^r^1;l>>=1,r>>=1){ if(~l&1){ val[l+1]+=v; sum[l+1]+=v*len[l+1]; } if(r&1){ val[r-1]+=v; sum[r-1]+=v*len[r-1]; } sum[l>>1]=sum[l]+sum[l^1]+val[l>>1]*len[l>>1]; sum[r>>1]=sum[r]+sum[r^1]+val[r>>1]*len[r>>1]; } while(l>1)sum[l>>1]=sum[l]+sum[l^1]+val[l>>1]*len[l>>1],l>>=1;}
ll query(ll l,ll r){ ll resl=0,resr=0; ll lenl=0,lenr=0; for(l+=length-1,r+=length+1;l^r^1;l>>=1,r>>=1){ if(~l&1){ resl+=sum[l+1]; lenl+=len[l+1]; } if(r&1){ resr+=sum[r-1]; lenr+=len[r-1]; } resl+=lenl*val[l>>1]; resr+=lenr*val[r>>1]; } resl+=resr; lenl+=lenr; while(l>1)resl+=lenl*val[l>>1],l>>=1; return resl;}
int main(){ int n,m; scanf("%d%d",&n,&m); build(n); for(int i=0;i<m;i++){ int t=read(),x=read(),y=read(); if(t==1){ ll v; v=read(); add(x,y,v); }else printf("%lld\n",query(x,y)); } return 0;}