导入
概念：
1>线段树的结构：
线段树是一种二叉搜索树。
2>用途：
1.在线维护修改以及查询区间上的最值，求和。
2.扩充到二维线段树（矩阵树）和三维线段树（空间树）。
3>时间复杂度：
对于一维线段树来说，每次更新以及查询的时间复杂度为O(logN)。
线段树
基本内容
对于A[1:6] = {1,8,6,4,3,5}来说，线段树如上所示，红色代表每个结点存储的区间，蓝色代表该区间最值。
可以发现，每个叶子结点的值就是数组的值，每个非叶子结点的度都为二，且左右两个孩子分别存储父亲一半的区间。每个父亲的存储的值也就是两个孩子存储的值的最大值。
对于一个区间[l,r]来说，最重要的数据当然就是区间的左右端点l和r，但是大部分的情况我们并不会去存储这两个数值，而是通过递归的传参方式进行传递。这种方式用指针好实现，定义两个左右子树递归即可，但是指针表示过于繁琐，而且不方便各种操作，大部分的线段树都是使用数组进行表示，那这里怎么快速使用下标找到左右子树呢。
对于上述线段树，我们增加绿色数字为每个结点的下标
注意：无优化的线段树建树需要2*2k（2k-1 < n < 2k)空间，一般会开到4*n的空间防止RE。
易知：1.每个左子树的下标都是偶数，右子树的下标都是奇数且为左子树下标+1
2. l= fa*2
3.r = fa*2+1
推论：以k为父节点的编号有：左子树编号为k<<1,右子树编号为k<<1|1;
code：
线段树的基本操作
1.点更新
更新一个子节点，则每个包含此值的结点都需要更新，于是我们可以用递归查找哪个子节点需要修改，在回溯的时候改变父节点的值。
code：
2.区间查询
我们可以将要查询的区间分配到个个节点中，在递归的同时判断所要查询的区间是否能够完全包含当前节点所代表的区间
1.完全包含,返回该节点上的值。
2.不完全包含，将该查询任务下发到左右子节点中。
3.完全分离，退出该节点。
code：
3.区间更新
在树状数组中我们利用差分进行区间修改，但这种方法在线段数中不适用，于是我们引入懒标记这一新概念。
懒标记：
在更新时不递归到子节点，而是判断所要修改的区间是否完全包含该节点的区间，像上面一样我们分为3种情况讨论：
1.完全包含,在该点上进行标记。
2.不完全包含，将该查询任务下发到左右子节点中。
3.完全分离，退出该节点。
注意：在递归到该节点的时候要先把该节点上原有的标记下传，再覆盖该节点的标记。
线段树的其他操作
扫描线
这是扫描线的模板题，但因为x,y是实数，所以要用离散化+二分查找。
扫描线：
下图每个矩形可以看做一个地图，矩形的总面积是我们要求的
首先呢，我们可以对每个矩形以所有与y轴平行的线进行切割，得到下面这个图
然后存入每一条线的位置，枚举所有矩形，将矩形拆分成两个四元组（x,y1,y2,k)，
x表示位置，
y1表示线段的起始位置，y2表示线段的末位置。
k=1表示该线段是矩形的最左边。
k=2表示该线段是矩形的最右边。
再以x为标准，从小到大排序。
线段树内存储在（xi-1-xi)这个区间内线段的总长度。
每次在修改之后只要ans+=len*(xi-xi-1)即可。
线段树中 cnt表示这一段被覆盖了几次。
ac代码：
1 #include <bits/stdc++.h> 2 #define N 1000000 3 using namespace std; 4 struct edge 5 { 6 double x,y1,y2; 7 int k; 8 bool friend operator <(const edge &t,const edge &y) 9 { 10 return y.x<t.x; 11 } 12 }op[N]; 13 struct node 14 { 15 int l,r,cnt; 16 double len; 17 }tr[4*N]; 18 vector<double>v; 19 void pushup(int u) 20 { 21 if(tr[u].cnt)tr[u].len=v[tr[u].r+1]-v[tr[u].l]; 22 else if(tr[u].l!=tr[u].r) tr[u].len=tr[u<<1].len+tr[u<<1|1].len; 23 else tr[u].len=0; 24 } 25 26 void modify(int u,int l,int r,int k) 27 { 28 if(l<=tr[u].l&&r>=tr[u].r){tr[u].cnt+=k;pushup(u);return;} 29 int mid=tr[u].l+tr[u].r>>1; 30 if(l<=mid)modify(u<<1,l,r,k); 31 if(r>mid) modify(u<<1|1,l,r,k); 32 pushup(u); 33 } 34 } 35 36 void build(int u,int l,int r) 37 { 38 if(l==r){tr[u]={l,r,0,0};return;} 39 else 40 { 41 int mid=(l+r)>>1; 42 tr[u]={l,r,0,0}; 43 build(u<<1,l,mid); 44 build(u<<1|1,mid+1,r); 45 } 46 } 47 48 int find(double x) 49 { 50 return lower_bound(v.begin(),v.end(),x)-v.begin(); 51 } 52 int main() 53 { 54 int n,T=1; 55 while(cin>>n&&n) 56 { 57 v.clear(); 58 for(int i=0,j=0;i<n;i++) 59 { 60 double x1,y1,x2,y2; 61 scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); 62 op[j++]={x1,y1,y2,1}; 63 op[j++]={x2,y1,y2,-1}; 64 v.push_back(y1);v.push_back(y2); 65 } 66 sort(v.begin(),v.end()); 67 v.erase(unique(v.begin(),v.end()),v.end()); 68 build(1,0,v.size()-2); 69 sort(op,op+2*n); 70 double ans=0.0; 71 for(int i=0;i<2*n;i++) 72 { 73 if(i>0) ans+=tr[1].len*(op[i].x-op[i-1].x); 74 modify(1,find(op[i].y1),find(op[i].y2)-1,op[i].k); 75 } 76 printf("Test case #%d\n",T++); 77 printf("Total explored area: %.2lf\n",-ans); 78 puts(""); 79 } 80 return 0; 81 }
线段树的一些重难点以及技巧（我会的）
1.离散化
常用于二维状态在一维线段树建树，所谓离散化就是将无限的个体映射到有限个体中，提高算法效率，而且支持正查和反查（从开始遍历和从末尾遍历），可用Hash等实现。
2.懒标记
这个标记就是用于线段树的区间更新，上面已经提到，便不再累赘，但是区间更新并不局限于使用Lazy_tag。。
3.空间优化
父节点k，左儿子k<<1，右儿子k<<1|1，则需要n<<2的空间，但我们知道并不是所有的叶子节点都占用到了2*n+1 —4*n的范围，造成了大量空间浪费。这时候就要考虑离散化，压缩空间。或者使用dfs序作为结点下标，父亲k，左儿子k+1，右儿子k+左儿子区间长度*2，具体实现不再累赘，可自行通过修改左右儿子的下标推出。
4.多维推广
例如矩阵树，空间树，这些便是线段树的拓展，比如要在两种不同的参数找到最适变量，例如对于一个人的身高和体重，找到一定范围内且年龄最小的人，就可以用到多维推广了。
5.可持久化
主席树。
6.非递归形式
前面提到过这个概念，非递归形式的某些操作会快于递归形式，以后将会专门将非递归形式。
7.子树收缩
就是子树继承的逆过程，继承是为了得到父节点信息，而收缩则是在回溯时候，如果两棵子树拥有相同数据的时候在将数据传递给父结点，子树的数据清空，这样下次在访问的时候就可以减少访问的结点数。