线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN）。而未优化的空间复杂度为2N，因此有时需要离散化让空间压缩。
#include<algorithm> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<vector> #include<queue> #include<stack> #include<iomanip> #include<string> #include<climits> #include<cmath> #include<time.h> #define MAX 120000 using namespace std; int n,m; int ans; struct Tree { int l,r; int sum,add; }; Tree tree[MAX*3]; void pushup(int x) { int tmp=2*x; tree[x].sum=tree[tmp].sum+tree[tmp+1].sum; } void pushdown(int x) { int tmp=2*x; tree[tmp].add+=tree[x].add; tree[tmp+1].add+=tree[x].add; tree[tmp].sum+=tree[x].add*(tree[tmp].r-tree[tmp].l+1); tree[tmp+1].sum+=tree[x].add*(tree[tmp+1].r-tree[tmp+1].l+1); tree[x].add=0; } void build(int l,int r,int x) { tree[x].l=l; tree[x].r=r; tree[x].add=0; if(l==r) { tree[x].sum=0; return ; } int tmp=x<<1; int mid=(l+r)>>1; build(l,mid,tmp); build(mid+1,r,tmp+1); pushup(x); } void update(int l,int r,int c,int x) { if(r<tree[x].l||l>tree[x].r) return ; if(l<=tree[x].l&&r>=tree[x].r) { tree[x].add+=c; tree[x].sum+=c*(tree[x].r-tree[x].l+1); return ; } if(tree[x].add) pushdown(x); int tmp=x<<1; update(l,r,c,tmp); update(l,r,c,tmp+1); pushup(x); } void query(int l,int r,int x) { if(r<tree[x].l||l>tree[x].r) return ; if(l<=tree[x].l&&r>=tree[x].r) { ans+=tree[x].sum; return ; } if(tree[x].add) pushdown(x); int tmp=x<<1; int mid=(tree[x].l+tree[x].r)>>1; if(r<=mid) query(l,r,tmp); else if(l>mid) query(l,r,tmp+1); else { query(l,mid,tmp); query(mid+1,r,tmp+1); } } int main() { //freopen("input2.txt","r",stdin); //freopen("output2.txt","w",stdout); scanf("%d %d",&n,&m); build(1,n,1);//建树 int str0; while(m--){ scanf("%d",&str0); if(str0==2){ int l; scanf("%d",&l); ans=0; query(l,l,1); printf("%d\n",ans); } else if(str0==1){ int l,r; scanf("%d %d",&l,&r); update(l,r,1,1); } } return 0; }
原文：http://www.cnblogs.com/zeze/p/6253996.html