线段树（一）——概念和应用
一、线段树概念
从简单说起，线段树其实可以理解成一种特殊的二叉树。但是这种二叉树较为平衡，和静态二叉树一样，都是提前已经建立好的树形结构。针对性强，所以效率要高。这里又想到了一句题外话：动态和静态的差别。动态结构较为灵活，但是速度较慢；静态结构节省内存，速度较快。只有PushUp()操作引起数据结构的改变，而只有在build()和update()时候才会调用PushUp()，所以线段树大体上是静态，但在"建立build()"和"更新update()"时是动态的!????? 接着回到线段树上来，线段树是建立在线段的基础上，每个结点都代表了一条线段[a , b]。长度为1的线段成为元线段。非元线段都有两个子结点，左结点代表的线段为[a , (a + b ) / 2]，右结点代表的线段为[( a + b ) / 2 , b]。
注意：1.?图中标注数字在实际应用中均作为下标使用! 例如sum[1,2, ... , 10]
?? ? ? ? ? ?2. 本图中的线段树是表示的是连续的范围；若表示离散的范围，则父亲i范围为[a,b]（a<b，否则a=b没有儿子），左儿子i*2范围为[a,(a+b)/2]，右儿子i*2+1范围为[(a+b)/2+1,b]
?? ? ? ? ? ?3. 节点序号i从1开始（根节点为1），这样才能保证“父亲序号i的，左儿子序号为i*2，右儿子序号为i*2+1”！
?? ? ? ? ? ? ? ?如果根节点序号为0，OMG！
?
?? ? ? ? ?图一就是一棵长度范围为[1 , 10]的线段树。长度范围为[1 , L] 的一棵线段树的深度为log ( L - 1 ) + 1。这个显然，而且存储一棵线段树的空间复杂度为O（L）。线段树支持最基本的操作为插入和删除一条线段。下面已插入为例，详细叙述，删除类似。将一条线段[a , b] 插入到代表线段[l , r]的结点p中，如果p不是元线段，那么令mid＝（l＋r）/2。如果a<mid，那么将线段[a , b] 也插入到p的左儿子结点中，如果b>mid，那么将线段[a , b] 也插入到p的右儿子结点中。插入（删除）操作的时间复杂度为O （ Log n ）。?上面的都是些基本的线段树结构，但只有这些并不能做什么，就好比一个程序有输入没输出，根本没有任何用处。最简单的应用就是记录线段有否被覆盖，并随时查询当前被覆盖线段的总长度。那么此时可以在结点结构中加入一个变量int count；代表当前结点代表的子树中被覆盖的线段长度和。这样就要在插入（删除）当中维护这个count值，于是当前的覆盖总值就是根节点的count值了。另外也可以将count换成bool cover；支持查找一个结点或线段是否被覆盖。
?
参见“http://andyzh1314.ycool.com/post.1050703.html”
?
二、线段树举例
参见“http://www.notonlysuccess.com/index.php/segment-tree-complete/”，有很多例子
?
1. 单点更新
??? 敌兵布阵--> http://acm.hdu.edu.cn/showproblem.php?pid=1166
??
??? A Simple Problem with Integers --> http://poj.org/problem?id=3468
??? *下面“灰底”部分为与单点更新的区别（对单点更新的扩充）
?
#include <cstdio>
#include <algorithm>
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
#define LL long long
const int maxn = 111111;
LL add[maxn<<2];//延迟标记：当前区间的值。为了减少更新时复杂度
LL sum[maxn<<2];
void PushUp(int rt) {
??? sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}?
//延迟标记从子树根下推1次（树根为rt，子树表示区间的长度为m）
void PushDown(int rt,int m) {
??? //1. add[rt]的值表示：节点rt对应线段区间中所有元线段的增量
??? //2. 如果当前结点有延迟标志，则向下推送，然后置0
??? if (add[rt]) {
??? ??? add[rt<<1] += add[rt];
??? ??? add[rt<<1|1] += add[rt];
??? ??? sum[rt<<1] += add[rt] * (m - (m >> 1)); //左儿子rt<<1对应线段区间[1,m>>1]的长度
??? ??? sum[rt<<1|1] += add[rt] * (m >> 1);???? //右儿子rt<<1|1对应线段区间[m>>1|1,m]的长度
??? ??? add[rt] = 0;
??? }
}
//build()同单点更新!
void build(int l,int r,int rt) {
??? add[rt] = 0;
??? if (l == r) {
??? ??? scanf("%lld",&sum[rt]);
??? ??? return ;
??? }
??? int m = (l + r) >> 1;
??? build(lson);
??? build(rson);
??? PushUp(rt);
}
/////////////////////////////////////////////////////////////////////////////////////////////用户需要将区间[L,R]内所有元线段都+c
//在子树[l,r](rt为根)去更新
void update(int L,int R,int c,int l,int r,int rt) {
??? if (L <= l && r <= R) {
??? ??? add[rt] += c;??? //A. 查询时，只有那些线段区间内所有元线段都要被更新的结点（不必再每次调用update()时就更新到“元线段”结点）才有add[i]+=c；其他结点add[j]=0
??? ??? sum[rt] += (LL)c * (r - l + 1);
??? ??? return ;
??? }
??? PushDown(rt , r - l + 1);
??? int m = (l + r) >> 1;?? //试探更新的区间二分为两端[l,m], [m+1,r]
??? if (L <= m) update(L , R , c , lson);
??? if (m < R) update(L , R , c , rson);
??? PushUp(rt);
}?
//用户需要查询区间[L,R]
//在子树[l,r](rt为根)去查询
LL query(int L,int R,int l,int r,int rt) {
??? if (L <= l && r <= R) {
??? ??? return sum[rt];
??? }
??? PushDown(rt , r - l + 1);??? //B. 当查询到某个范围时，如果之前没有更新到“结点rt”以下的结点，才向下更新所有“以rt为根子树中的结点的add[i]和sum[i]”。这样做为了加快update()速度
??? //询问一段，才去查询一段的值(通过if类判定)
??? int m = (l + r) >> 1;
??? LL ret = 0;
??? if (L <= m) ret += query(L , R , lson);??? //[l,m]，包含m
??? if (m < R) ret += query(L , R , rson);???? //(m,r]
??? return ret;
}
int main() {
??? int N , Q;
??? scanf("%d%d",&N,&Q);
??? build(1 , N , 1);
??? while (Q --) {
??? ??? char op[2];
??? ??? int a , b , c;
??? ??? scanf("%s",op);
??? ??? if (op[0] == 'Q') {
??? ??? ??? scanf("%d%d",&a,&b);
??? ??? ??? printf("%lld\n",query(a , b , 1 , N , 1));
??? ??? ??? //1. %lld 对应long long的十进制
??? ??? ??? //2. query(a,b,1,N,1) 前2个参数是查询问题，后3个参数指定线段树的范围
??? ??? } else {
??? ??? ??? scanf("%d%d%d",&a,&b,&c);
??? ??? ??? update(a , b , c , 1 , N , 1);
??? ??? }
??? }
??? return 0;
}?
3. 区间合并
这类题目会询问区间中满足条件的连续最长区间,所以PushUp的时候需要对左右儿子的区间进行合并：
????? 3中情况（这是动态规划的思想/子问题结构）
???????????????????? （1）最长区间在rt的左子树中；
???????????????????? （2）最长区间在rt的右子树中；
???????????????????? （3）最长区间取 “rt左子树‘贴着她的右端点’的区间”+“rt右子树‘贴着她的左端点’的区间”
?
hotel -->http://poj.org/problem?id=3667
Atlantis面积合并 --> http://acm.hdu.edu.cn/showproblem.php?pid=1542
#include <cstdio>#include <cstring>#include <cctype>#include <algorithm>using namespace std;#define lson l , m , rt << 1#define rson m + 1 , r , rt << 1 | 1const int maxn = 2222;int cnt[maxn << 2];//对于rt，若cnt[rt]>0，则对应子树的线段区间被完全覆盖；若cnt[rt]==0，则被部分覆盖/完全没有覆盖double sum[maxn << 2];//对于rt,sum[rt]为对应子树覆盖的到线段区间的长度double X[maxn];//所有矩形的左右边界“直线”（每个矩形有两条这种直线，分别占用本数组的两个元素）//（矩形）上/下边界“线段”struct Seg {double h , l , r;//h高度, l左端点, r右端点int s;//s==1为下边界线段； s==-1为上边界线段Seg(){}Seg(double a,double b,double c,int d) : l(a) , r(b) , h(c) , s(d) {}//需要按照上/下边界线段的高度来排序bool operator < (const Seg &cmp) const {//看运算符重载???return h < cmp.h;}}ss[maxn];void PushUp(int rt,int l,int r) {if (cnt[rt]) sum[rt] = X[r+1] - X[l];//子树rt的线段区间完全覆盖else sum[rt] = sum[rt<<1] + sum[rt<<1|1];//子树rt的线段区间没有完全覆盖（没有覆盖/部分覆盖）}//需要插入/移出线段树的“上/下边界线段”： 左端点X[L], 右端点X[R+1], c==1下边界/c==-1上边界//待插入/移除的线段树子树范围void update(int L,int R,int c,int l,int r,int rt) {if (L <= l && r <= R) {cnt[rt] += c;PushUp(rt , l , r);return ;}int m = (l + r) >> 1;if (L <= m) update(L , R , c , lson);if (m < R) update(L , R , c , rson);PushUp(rt , l , r);}int Bin(double key,int n,double X[]) {int l = 0 , r = n - 1;while (l <= r) {int m = (l + r) >> 1;//1. 第1个分支是“递归终止条件”if (X[m] == key) return m;//2. 第2、3个分支是“二分后的两个子问题”if (X[m] < key) l = m + 1;else r = m - 1;}return -1;}int main() {int n , cas = 1;while (~scanf("%d",&n) && n) {int m = 0;while (n --) {double a , b , c , d;scanf("%lf%lf%lf%lf",&a,&b,&c,&d);X[m] = a;ss[m++] = Seg(a , c , b , 1);X[m] = c;ss[m++] = Seg(a , c , d , -1);}sort(X , X + m);sort(ss , ss + m);//X[]已经递增排序后，如下操作使得X[]中不等的数字依次放在靠前//例如X[]={1,2,2,5,5,7} --> X[]={1,2,5,7,5,7}//处理后，其中X[0, ... ,k-1]为不等的数字int k = 1;for (int i = 1 ; i < m ; i ++) {if (X[i] != X[i-1]) X[k++] = X[i];}memset(cnt , 0 , sizeof(cnt));memset(sum , 0 , sizeof(sum));//下面为m-1轮扫描的过程double ret = 0;for (int i = 0 ; i < m - 1 ; i ++) { //i=0-->m-2int l = Bin(ss[i].l , k , X);int r = Bin(ss[i].r , k , X) - 1;//“上/下边界线段”长度不为0时，采取更新线段树。否则，这种“上/下边界线段”横向收缩为一个点if (l <= r) update(l , r , ss[i].s , 0 , k - 1, 1);//每轮扫描：更新线段树后，累计本轮扫描新增的面积大小ret += sum[1] * (ss[i+1].h - ss[i].h);}printf("Test case #%d\nTotal explored area: %.2lf\n\n",cas++ , ret);}return 0;}??
?
