首页 > 代码库 > 线段树
线段树
线段树与BST不同，它维护的是区间信息，树高越低，区间范围越大，而最后一层就是单点信息。线段树的价值于其维护的区间信息，如果不能有效利用，那么线段树就是一颗废树。
一、单点更新
线段树按照结点更新方式的不同，分为单点更新和成段更新。单点更新是线段树最简单的结构。通常由Push_Up, Build,Update,Query四个操作构成。其中Push_Up代码最简单，但却是线段树的核心，它负责区间信息的向上更新，换言之，如果设计不 出有效的Push_Up,那么线段树就是颗废树。
#include "iostream"#include "string"#include "vector"#include "cstring"#include "fstream"#include "cstdio"using namespace std;#define M 50001#define lson l,mid,root<<1#define rson mid+1,r,root<<1|1int sum[M<<2];void PushUp(int root){ sum[root]=sum[root<<1]+sum[root<<1|1];}void build(int l,int r,int root){ if(l==r) { scanf("%d",&sum[root]); return; } int mid=(l+r)>>1; build(lson); build(rson); PushUp(root);}void update(int p,int value,int l,int r,int root){ if(l==r) { sum[root]=value; return; } int mid=(l+r)>>1; if(p<=mid) update(p,value,lson); else update(p,value,rson); PushUp(root);}int qurry(int L,int R,int l,int r,int root){ if(L<=l&&r<=R) return sum[root]; int mid=(l+r)>>1; int ret=0; if(L<=mid) ret+=qurry(L,R,lson); if(R>mid) ret+=qurry(L,R,rson); return ret;}
上面的线段树风格来自Hdu的神犇NotOnlySuccess，他的那篇线段树总结写的很好，不过个人主页经常挂。orz。
线段树是大量数据时代，首先得抛弃使用cin的坏习惯。Windows下，不关sync的cin时间是scanf的10倍，关了也有2~3倍，100%会超时。Linux下关了sync的cin倒是比scanf快。
根据Push_Up操作，大致可以分为以下几类。
sum[root]=sum[root<<1]+sum[root<<1|1]
@练习题
HDU 1166, 线段树求和模板题，更新之后查询即可。
XCOJ 1019, 阉割掉Update的线段树，其实用树状数组做更好。坑的地方是有重复点，要叠加。
2. 区间RMQ（范围最值查询）
RMQ[root]=max(RMQ[root<<1],RMQ[root<<1|1]);
@练习题
二、成段更新
void build(int l,int r,int root){ col[root]=-1; //多组数据，标记清除}void PushDown(int root,int m){ if(col[root]!=-1) { col[root<<1]=col[root<<1|1]=col[root]; sum[root<<1]=col[root]*(m-(m>>1)); sum[root<<1|1]=col[root]*(m>>1); col[root]=-1; }}void update(int L,int R,int c,int l,int r,int root){ if(L<=l&&r<=R) { col[root]=c; sum[root]=c*(r-l+1); return; } PushDown(root,r-l+1); int mid=(l+r)>>1; if(L<=mid) update(L,R,c,lson); if(R>mid) update(L,R,c,rson); PushUp(root);}int query(int L,int R,int l,int r,int root){ if(L<=l&&r<=R) return sum[root]; PushDown(root,r-l+1); //这里的PushDown很重要 //下同单点更新}
通俗点说，离散化就是压缩区间，使原有的长区间映射到新的短区间，但是区间压缩前后的覆盖关系不变。举个例子：
有一条1到10的数轴（长度为9），给定4个区间[2,4] [3,6] [8,10] [6,9]，覆盖关系就是后者覆盖前者，每个区间染色依次为 1 2 3 4。
现在我们抽取这4个区间的8个端点，2 4 3 6 8 10 6 9
然后删除相同的端点，这里相同的端点为6，则剩下2 4 3 6 8 10 9
对其升序排序，得2 3 4 6 8 9 10
然后建立映射
2 3 4 6 8 9 10
↓ ↓ ↓ ↓ ↓ ↓ ↓
1 2 3 4 5 6 7
那么新的4个区间为 [1,3] [2,4] [5,7] [4,6]，覆盖关系没有被改变。新数轴为1到7，即原数轴的长度从9压缩到6，显然构造[1,7]的线段树比构造[1,10]的线段树更省空间，搜索也更快，但是求解的结果却是一致的。
离散化时有一点必须要注意的，就是必须先剔除相同端点后再排序，这样可以减少参与排序元素的个数，节省时间。
void query(int *col,bool *Hash,int l,int r,int root){ if (col[root]) { if (!Hash[col[root]]) cnt++; Hash[col[root]] = true; return; } PushDown(col,root,r-l+1); if (l==r) return ; int mid = (l + r) >> 1; query(col,Hash,lson); query(col,Hash,rson);}
线段树