扫描线与线段树在解决连续区间问题中的应用

线段树入门 线段树是一种高效的数据结构，主要用于解决连续区间的动态查询问题。它是一棵二叉搜索树，每个节点保存一条线段，主要用于高效解决连续区间的动态查询问题。 线段树的定义是根据每个矩形纵向边的横坐标纵向地对平面进行2*n次切割、根据矩形横向边的纵坐标横向地对矩形进行2*n次切割（n为矩形个数），切割后得到的矩形的被切割后的小段边就是超元线段。现在我们仅考虑未被横向的边切割的超元线段（即矩形纵向的边），这些边上的直线把矩形分成这2*n-1块区域，而这些区域的面积和也就是矩形并后的面积。 如何求每一块区域的面积呢？长可以通过两条相邻的超元线段的x坐标差得到（即line[i].x-line[i-1].x）。如果求出宽呢？宽就是line[i]之前（不包括i）的所有线段全部投影到y轴上得到的长度，也就是说我们求出y轴上被覆盖的区域的长度即可。 线段树的实现方法是用维段树去维护。当我们从左往右不断地将线段放入线段树以求得在y轴上投影得到的区域的长度时，我们把同一个矩形左边的边的权值设置为1（表示覆盖），右边的边设置为-1（表示撤消覆盖）。这样就能实现对y轴上投影的更新，因为这是假想有一根线去不断地从左往右扫，所以叫扫描线。 线段树的性质有： * 线段树是一棵平衡树，树的高度为logN。 * 线段树把区间上任意长度为L的线段都分成不超过2logL条线段的并 * 任意两个结点要么是包含关系，要么没有公共部分，不可能重叠 * 给定一个叶子P，从根到P路径上所有结点代表的区间都包含P，其他结点代表的区间都不包含P 线段树的应用场景是当我们需要解决一些跟区间有关的问题时，例如给一些区间线段求并区间的长度，或者并区间的个数等等。这些问题的描述都非常简单，但是通常情况下数据范围会非常大，而朴素方法的时间复杂度过高，导致不能在规定时间内得到问题的解。这时，我们需要一种高效的数据结构来处理这样的问题，那就是线段树。 线段树的基本结构是一棵二叉搜索树，每个节点保存一条线段。例如，一棵线段树可以表示为： [1,10] 每个区间单元 对应树中的 [1,5][6,10] 叶节点 [1,3][4,5][6,8][9,10] [1,2][3,3][4,4][5,5][6,7][8,8][9,9][10,10] [1,1][2,2][6,6][7,7] 线段树可以用来解决一些复杂的问题，例如求某个数组的某个区间和等。线段树是一种非常有用的数据结构，可以帮助我们高效解决一些连续区间的动态查询问题。