线段树总结
转载请注明出处：http://blog.csdn.net/a1dark
学了一段时间的线段树、始终没有没有形成自己的风格、于是重头再来一遍、以HH大牛的线段树分类、单点更新、成段更新、区间合并、扫描线、重新梳理一遍自己的线段树知识、
单点更新：【HDU 1166 敌兵布阵】
分析：单点更新还是挺容易的、就是建立一颗二叉树、用来表示区间、可以优化查询时间和更新时间、
#include<stdio.h>#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1#define maxn 100005struct segmentTree{ int sum; int col;}tree[maxn<<2];void PushUp(int rt){ tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;}void build(int l,int r,int rt){ tree[rt].col=0; if(l==r){ tree[rt].sum=1; return; } int mid=(l+r)/2; build(lson); build(rson); PushUp(rt);}void PushDown(int rt,int len){ if(tree[rt].col){ tree[rt<<1].col=tree[rt<<1|1].col=tree[rt].col; tree[rt<<1].sum=(len-len/2)*tree[rt].col; tree[rt<<1|1].sum=(len/2)*tree[rt].col; tree[rt].col=0; }}void update(int a,int b,int c,int l,int r,int rt){ if(a<=l&&b>=r){ tree[rt].col=c; tree[rt].sum=c*(r-l+1); return; } PushDown(rt,r-l+1); int mid=(l+r)/2; if(a<=mid)update(a,b,c,lson); if(b>mid)update(a,b,c,rson); PushUp(rt);}int main(){ int t,n,m,cas=1; scanf("%d",&t); while(t--){ scanf("%d",&n); build(1,n,1); scanf("%d",&m); int a,b,v; for(int i=1;i<=m;i++){ scanf("%d%d%d",&a,&b,&v); update(a,b,v,1,n,1); } printf("Case %d: The total value of the hook is %d.\n",cas++,tree[1].sum); } return 0;}