线段树算是一种较为简单的中级数据结构了，线段树本身其实还是很简单的，就是一棵二叉树，每一个节点维护一块区间的信息，如果根节点是$[1,n]$，那么左儿子就是$[1,n/2]$,右儿子就是$[n/2+1,n]$，如此二分下去就是一棵线段树了，查找的时间复杂度是$O(log2n)$的，有图为证：(网上找的)
下面是某线段树模板题的代码：
#include <cstdio> #include <algorithm> using namespace std; typedef long long LL; static const int maxm=1e6+10; LL tree[maxm],lazy[maxm],A[maxm],left[maxm],right[maxm]; int n,m; void build(int num,int l,int r){ left[num]=l;right[num]=r; int mid=(l+r)>>1; if(l==r){ tree[num]=A[l]; return; } build(num<<1,l,mid); build(num<<1|1,mid+1,r); tree[num]=tree[num<<1]+tree[num<<1|1]; } void pushdown(int num){ if(lazy[num]){ int mid=(left[num]+right[num])>>1; tree[num<<1]+=(mid-left[num]+1)*lazy[num]; tree[num<<1|1]+=(right[num]-mid)*lazy[num]; lazy[num<<1]+=lazy[num]; lazy[num<<1|1]+=lazy[num]; lazy[num]=0; } } void update(int num,int l,int r,LL add){ if(left[num]>=l&&right[num]<=r){ tree[num]+=(right[num]-left[num]+1)*add; lazy[num]+=add; return; } if(left[num]>r||right[num]<l)return; pushdown(num); update(num<<1,l,r,add); update(num<<1|1,l,r,add); tree[num]=tree[num<<1]+tree[num<<1|1]; } LL Query(int num,int l,int r){ if(left[num]>=l&&right[num]<=r)return tree[num]; if(left[num]>r||right[num]<l) return 0; LL ret=0; pushdown(num); ret+=Query(num<<1,l,r); ret+=Query(num<<1|1,l,r); return ret; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%lld",&A[i]); build(1,1,n); for(int i=1;i<=m;i++){ int f,x,y;LL add; scanf("%d",&f); switch(f){ case 1:scanf("%d%d%lld",&x,&y,&add);update(1,x,y,add);break; case 2:scanf("%d%d",&x,&y);printf("%lld\n",Query(1,x,y));break; default:printf("Orz %%%");break; } } return 0; }
原文：http://www.cnblogs.com/Exbilar/p/6388902.html
