本节书摘来自华章计算机《程序设计解题策略》一书中的第1章，第1.3节,作者：吴永辉 王建德 更多章节内容可以访问云栖社区“华章计算机”公众号查看。
在现实生活中，我们经常遇到与区间有关的问题，例如，记录一个区间的最值(最大或最小值)和总量，并在区间的插入、删除、修改中维护这些最值和总量；再如，统计若干矩形并的面积。线段树拥有良好的树形二分特征，我们可以从其定义和结构中发现，在线段树的基础上完成这些问题的计算操作，是十分简捷和高效的。1.3.1 线段树的基本概念
一棵二叉树，记为T(a，b)，参数a、b表示该节点表示区间［a，b］。区间的长度b-a记为L。递归定义T［a，b］： 若区间长度L>1：区间［a，(a+b)div2］为T的左儿子，区间［(a+b)div2，b］为T的右儿子。 若区间长度L=1：T为一个叶子节点，表示区间［a，a+1］。 例如，区间［1，10］的线段树表示如图1.3-1所示。 【定理1.3-1】 线段树把区间上的任意一条线段都分成不超过2*log2L条线段。 证明：我们首先从覆盖区间的线段开始讨论，然后推广至任意线段。 1) 在区间(a，b)中，如果线段(c，d)满足(c≤a)或(d≥b)，则该线段在区间(a，b)中被拆分的线段数不超过log2(b-a)条。 用归纳法证明： 如果是单位区间，最多被分为一段，成立。 如果区间(a，b)的左儿子与右儿子成立，那么如果当c≤a时，则有两种情况： ① 若 ，则该线段拆分为它左儿子区间的线段，线段数不超过log2a+b2」-a，即不超过log2(b-a)，成立； ② 若 ，则相当于该线段被拆分为它左儿子区间的线段和右儿子区间的线段，线段数不超过 ，也不超过log2(b-a)，成立。 对于d≥b的情况证明类似，不再赘述。 2) 在区间(a，b)中，对于任意线段也用归纳法证明。 对于单位区间，最多分为一段，成立。 若(a，b)的左儿子与右儿子均成立，则对于线段(c，d)有三种情况。 情况1：若d≤a+b2」，则(c，d)被拆分为(a，b)的左儿子区间的线段，线段数小于log2a+b2」-a<2*log2(b-a)，成立。 情况2：若c>a+b2」，则(c，d)为(a，b)右儿子区间的线段，线段数小于log2b-a+b2」<2*log2(b-a)，成立。 情况3：若前两种情况均不成立，则(c，d)在(a，b)左儿子区间满足d>左儿子区间的右端点，被拆分出的线段数不超过log2b-a+b2」；而在(a，b)右儿子区间满足c≤右儿子区间的左端点，被拆分出的线段数不超过log2a+b2」-1，所以在(a，b)区间被拆分出的线段数不超过2*log2(b-a)条，成立。 由以上证明过程可以看出，线段树的构造实际上是用了二分的方法。线段树是平衡树，它的深度为log2(L)，能在O(log2L)的时间内完成一条线段的插入、删除、查找等工作。 节点的构造可以用如下数据结构： struct Node // 节点的结构定义 { int a,b,left,right,cover;// 代表区间［a,b］；指向左右子树的指针分别为left和 // right；节点基数（即覆盖［a,b］的线段数）为cover } Tree［Maxn］;// 数组Tree［］存储线段树，数组元素的类型定义为Node， // 数组下标为节点序号为了简化数据结构和方便计算，也可以采用静态数组a［］、b［］、cover［］、left［］、right［］存储线段树。设线段树的子树根为v，a［v］、b［v］就是v所表示区间的左右边界；cover［v］仍然用来作计数器；left［v］、right［v］分别为v的左儿子和右儿子的数组下标。注意，这只是线段树的基本结构。通常利用线段树解题的时候，需要在每个节点上增加一些特殊的数据域，并且它们是随线段的插入删除进行动态维护的。至于应该增加哪些数据域，因题而异。1.3.2 线段树的基本操作和拓展线段树的最基本的操作包括：1) 建立线段树T(a，b)。2) 将区间［c，d］插入线段树T(a，b)。3) 将区间［c，d］从线段树T(a，b)中删除。4) 线段树的动态维护。下面以静态数据结构为例，介绍这些基本操作：（1） 建立线段树T(a，b)设一个全局变量Tot，记录一共用到了多少节点。开始Tot=0。
void build(int a,int b) { int Now; Tot++;Now=Tot;// 代表区间［a，b］的变量初始化 Tree［Now］.a=a;Tree［Now］.b=b;Tree［Now］.cover=0; if(b-a>1)// 若该区间存在 { int mid=(a+b)>>1;// 计算中间指针 Tree［Now］.left=Tot+1;build(a,mid);// 给左儿子编号并递归左子区间 Tree［Now］.right=Tot+1;build(mid,b);// 给右儿子编号，并递归右子区间 } }（2） 将区间［c，d］插入以Num节点为根的线段树如果［c，d］完全覆盖了Num节点代表的区间［Tree［Num］.a，Tree［Num］.b］，那么显然该节点上的基数(即覆盖线段数)加1；否则，如果［c，d］不跨越区间中点，就只在左树或者右树上进行插入。如果［c，d］跨越区间中点，则在左树和右树上都要进行插入。注意观察插入的路径，一条待插入区间在某一个节点上进行“跨越”，此后两棵子树上都要向下插入，但是这种跨越不可能多次发生。插入区间的时间复杂度是O(log2n)。
void insert(int Num)// 将区间［c,d］插入以Num为根的线段树 { if(c<=Tree［Num］.a&&Tree［Num］.b<=d)// 若区间［c,d］覆盖v节点代表的区间，则覆盖该区间的 // 线段条数+1 Tree［Num］.cover++; Else// 否则，若［c,d］不跨越区间中点，就只对左树或右树上进行 // 插入；若［c,d］跨越区间中点，则在左树和右树上都要进行插入 { int mid=(Tree［Num］.a+Tree［Num］.b)>>1; if(c<=mid) insert(Tree［Num］.left); if(d>=mid) insert(Tree［Num］.right); } }（3） 将区间［c，d］从以Num节点为根的线段树中删除设线段树T(a，b)的根编号为v。在线段树上删除一个区间与插入的方法几乎是完全类似的。特别注意：只能删除曾经插入过的区间，这样才能保证线段树的维护是正确的。
void del(int Num)// 从以Num节点为根的线段树中删除区间［c,d］ { if(c<=Tree［Num］.a&&Tree［Num］.b<=d)// 若区间［c,d］覆盖Num节点代表的区间，则覆盖该区间的 // 线段条数-1；在区间［c,d］不覆盖Num节点代表的区间的情况下，若［c,d］不跨越区间中点，就只对左树或右树 // 上进行删除；否则在左树和右树上都要进行删除 Tree［Num］.cover--; else { int mid=(Tree［Num］.a+Tree［Num］.b)>>1; if(c<=mid)del(Tree［Num］.left); if(d>=mid)del(Tree［Num］.right); } }（4） 线段树的动态维护线段树的作用主要体现在可以方便地动态维护其某些特征。例如，增加一个全局变量Number，存储以Num为根的子树上线段并集的长度。我们采用前序遍历线段树的算法计算Number：若当前节点代表的区间被线段［Tree［Num］.b，Tree［Num］.a］覆盖(Tree［Num］.cover＞0)，则线段长度Tree［Num］.b-Tree［Num］.a累计入Number；否则分别递归左右子树：`javascriptvoid Count(int Num){if(Tree［Num］.cover)Number+=(Tree［Num］.b-Tree［Num］.a);else{if(Tree［Num］.left)Count(Tree［Num］.left);if(Tree［Num］.right)Count(Tree［Num］.right);}}
类似的，还有求并区间的个数等。这里不再深入列举。 （5） 线段树的合并 我们遇到的许多问题，往往可抽象成这样一个数学模型： 有一列元素a1 a2 … an∈S，S上有二元运算+，使得对于任意a，b∈S，都有a+b∈S，并且+满足结合律({S+}是半群)。另外，+运算必须能高效地计算完成，譬如O(1)。 要求高效地支持：修改某个ai，给定l、r，回答al al+1 … ar。 <div style="text-align: center"> <img src="https://yqfile.alicdn.com/f4f187c041c3c091ee1e7e81018e9faa3165a9c6.png " > </div> 由于运算有结合律，因此使用线段树来维护一些连续元素的和是一种有效的选择： 从［1，n］开始，把每段连续的元素尽可能均匀地分成两半，直到成为单个元素为止。这个关系构成了一棵近似丰满的二叉树，每个节点代表了一些连续或单个元素，我们在上面维护它们的和(见图1.3-2)。 显然，每个元素出现在O(logn)个维护的和当中，每个询问能表示成O(logn)个维护的和的和。当确定了元素个数n，或者key的范围［1，U］，建出的线段树形态是唯一的。对两棵key的上界相同的线段树进行参数相同的单点更新或区间询问时，所访问到的节点也是一致的。由此出现了线段树的合并。根据线段树的定义，不难写出合并的基本流程。void Merge（a,b）:{ 如果a、b中有一个不含任何元素，就返回另一个；如果a、b都是叶子，返回merge_leafab；返回merge（a->l，b->l）与merge（a->r，b->r）连接成的树}
由于a和b两棵线段树的树结构相同，上面过程的正确性是显然的。a、b中可能存在key相同的元素，之前对线段树的定义于这种情况无能为力，所以需要一个merge_leaf过程给出新树中该位置的元素。为了方便确定一棵树是否为空，动态开辟节点。若某棵子树为空，则其对应的父亲指针为空。例如，图1.3-3给出了合并两棵线段树后维护区间内数字个数的样例。 <div style="text-align: center"> <img src="https://yqfile.alicdn.com/2cdf35f87ab288370a842c8ff2157ace253839ed.png " > </div> 下面，我们来分析一下线段树合并的时间复杂度： 若merge_leaf过程和运算的代价都是O(1)，容易看出合并的开销正比于两棵树公共的节点数。单次merge操作的开销可大可小，但我们可以立即得到一个非常有用的结论： 若有n棵含有单个元素的树，经过n-1次merge操作，将它们合并成一棵的代价是O(n*log2n)或O(n*log2U)。 理由十分简单，n-1次merge操作的开销不会比向一棵空树顺序插入n个整数来的大。如果以合并操作为核心，则可以写出另一种风格的线段树。这种线段树可实现如下关键操作： 1) merge_leaf过程。 2) 连接操作。 3) merge过程。 4) make_leaf过程。 所有操作自顶向下，可以方便持久化。 在竞赛中，我们经常会遇到这样一类问题：要将若干物件不断合并，顺便计算一些信息。有些以树为背景的题目也需要完成类似的工作。其中很大一部分需要维护一些元素的有序序列。通常用平衡树的启发式合并解决，复杂度为O(n*(log2n)2)。若关键字为较小整数的话，换用线段树合并可降低复杂度的阶，做到O(n*log2n)或O(n*log2U)(U为区间长度)。 **1.3.3 应用线段树解题** 线段树主要是对区间线段的处理，因此往往被应用于几何计算问题中。比如在处理一组矩形问题时，用来求矩形并图后的轮廓周长和面积等，其运算效率比普通的离散化方法要高。 用线段树解题的一般方法是： 1) 分析试题，揭示问题的区间特征。 2) 根据要求构建线段树。一般情况下需要对坐标离散。建树时，不要拘泥于问题的原型是线段还是数值或是其他什么形式，只要能够表示成区间，而且区间是由单位元素(可以是一个点、一条线段或数组中一个值)组成的，都可以采用线段树模型；不要局限于一维，可以根据题目要求建立二维的面积树、三维的体积树等。关于二维面积树的计算，我们将在4.1.2节中介绍。 3) 线段树的每个节点可以根据题目所需，设置记录区间线段特征值的变量。 4) 用树型结构来维护这些变量：如果是求节点总数，则是左右子树的节点数和+1(加上子根)；如果要求最值，则是左右子树的最值再联系本区间。利用每次插入、删除时仅修改O(log2L)个节点这个特点，在O(log2L)的时间内维护修改后相关节点的变量。 5) 在非规则的删除操作和大规模修改数据的操作中，可以利用叶节点反映出区间内各种数据单一性的本质特征，灵活地将子树收缩为叶子或让被收缩的叶子释放还原出区间，从而避免重复操作，提高算法效率。 下面，我们通过范例揭示线段树的构建过程，引导读者怎样做到“三个学会”：学会揭示问题的区间特征，学会离散坐标并用相应的区间描述，学会为线段树每个节点设置记录区间情况的参数。 【1.3.1 Snake】 【问题描述】 给出平面上N个点的坐标，所有的坐标(xi，yi)是在闭区间-10000到10000范围内的整数。构造满足如下条件的一条折线： 1) 这条折线必须闭合。 2) 折线每段的端点只能是这给出的N个点。 3) 折线交于一点的两条线段构成90度角。 4) 折线的线段要与坐标轴平行。 5) 所有线段除在这N个点外，都不会相交。 6) 所有线段的长度之和必须最短。 请你给出构成这条折线的长度L，或者确定这N个点不可能构成一条折线。 输入： 第1行为点数N(1≤N≤10000)；以下N行，依次给出每个点的坐标xi和yi，用空格分开(1≤i≤N)。点的次序是任意的。 输出： 若存在满足条件的折线，则输出线段长度之和的最小值L；否则输出0。 <div style="text-align: center"> <img src="https://yqfile.alicdn.com/0db8bbad3994e1d939fbe9a2249bd47a7616005b.png " > </div> <div style="text-align: center"> <img src=" https://yqfile.alicdn.com/271eb22d1538ee7a2695305629f6a59afeb23df8.png" > </div> 坐标轴平行试题解析简述题意：给你N个点，让你用这N个点围城一个闭合的环，交点两边的线段组成90°的角，线段都平行于坐标轴，线段两两不相交，使线段长度和最短。 显然，题目是要求构建一个以给定的N个点为节点的N边形。所有线段都要和坐标轴平行，所以每个点只能与上下左右四个点相连。由于与一个点相连的两条线段成90度，每个节点必须与一条平行于X轴和一条平行于Y轴的线段相连，见图1.3-4。 将所有点分别按照X坐标和Y坐标排序后发现，在同一水平线上的点中，设这些点为P1，P2，P3，P4，…，Pn，P1要有一条平行于X轴的线段与其相连，就必须连它右边的点P2，而P3如果再连P2，P2就有两条平行于X轴的线段和它相连，所以P3只能连P4，P5只能连P6(见图1.3-5)。同一垂直线上的点也是如此，所以线段的构造是唯一的，那么最小长度的问题就解决了。 由于解是唯一的，而线段是否相连只要宽度优先搜索的顺序扩展就可以判断了，所以关键在于判断由上述方法所构造出的线段是否合法——满足线段不在N个点之外自交(见图1.3-6)。 <div style="text-align: center"> <img src="https://yqfile.alicdn.com/c38d559eaa879340a64267ead953347de0109b05.png" > </div> 由于所有线段与坐标轴之一平行，有明显的区间性，因此可以想到用线段树判断是否自交。 仅考虑与Y轴平行的线段是否有线段与之相交(因为相交的两条线段分别与X轴和Y轴平行)。如果线段(x，y1)-(x，y2)与线段(x1，y)-(x2，y)相交，则应该符合x1<x<x2和y1<y<y2(见图1.3-7)。 由条件(x1<x<x2)，可以想到先把所有的线段按X坐标排序。本题要注意的是，线段在端点重合不算自交，所以X轴坐标相同时，事件的顺序要恰当处理。如图1.3-8，右端点优先，与Y轴平行的线段其次，然后到左端点。 <div style="text-align: center"> <img src=" https://yqfile.alicdn.com/f12ca96696f7c7d0e336f4095bb38fbc6d4f587a.png" > </div> 将Y轴表示的区间建立线段树。排序后，每个线段或线段的端点称为一个事件，如图1.3-9，S1、S2、S3、S4分别为一个事件。 <div style="text-align: center"> <img src="https://yqfile.alicdn.com/d036d5c6854b00fdc4f7b5ab882304efb67e7f93.png " > </div> 按X坐标由小到大，扫描所有事件：如果遇到平行于X轴线段的左端点，则按它的Y坐标当成一个点，插入到表示Y轴区间的线段树中；如果遇到平行于X轴线段的右端点，则把它代表的点从线段树中删除；如果遇到与Y轴平行的线段L1(x，y1)-(x，y2)，假设有线段L2(x1，y)-(x2，y)与之相交，由x1<x<x2可知，L2的左端点已经被扫描过，那么L2代表的点已经插入线段树中；L2的右端点还没被扫描过，说明L2代表的点依然存在于线段树之中。换言之，只要还在线段树中的点，就满足x1<x<x2。要判断y1<y<y2的条件是否满足，可以在线段树中查找［y1+1，y2-1］(在端点处可以相交)区间内是否有点存在，如果存在，就说明有线段和它相交，该图形不合法。 具体实现时要注意线段树每个节点增加一个变量记录该区间内的点数，线段树的单位元(叶子节点)改成一个点，而不是一条单位线段。每次插入和删除后，只要对相关节点的变量进行改动就可以了。将Ｙ轴坐标离散后，以上过程每次执行插入、删除及查找过程的复杂度是O(log2n)级别的，由于所有线段数量是O(n)级别的，所以整题的时间复杂度是O(nlog2n)级别。 如果将本题扩展成求这些线段所有交点的个数，则只要在查找时把区间内的所有点统计出来就可以了。 程序清单using namespace std;
const int MAXN = 100000; // 点数的上限
struct ptype{// 点序列的元素类型int x, y, id;// 点坐标为（x,y），输入顺序为id};
struct stype{// 线段表的元素类型ptype p1, p2;// 线段两个端点的坐标};
ptype p［MAXN］;// 点序列 stype s［MAXN*2］;// 线段表，其中第i条线段为int pos［MAXN］［4］;// 连接点i的线段条数为pos［i,0］，其中第j条线段的// 序号为pos［i,j］ int a［2 MAXN］, aa［2 MAXN］;// y坐标序列int tree［3 * MAXN］;// y轴区间的线段树 int e［MAXN］［4］;// 连接点i的线段条数为e［i,0］，其中第j条线段的// 另一个端点序号为e［i,j］bool f［MAXN］;// 事件点的访问标志序列int n, m, sum, k, t;// 点数为n，最小长度为sum
void Init()// 输入信息{cin >> n;// 读入点数for (int i = 1; i <= n; ++i)// 读入每点坐标,记下输入顺序 { cin>>p［i］.x>>p［i］.y;p［i］.id=i; }}
bool Succ()// 构造线段，若线段间衔接，则返回最小长度和成功标志{int i, j, t;memset(s,0,sizeof(s)); m=0;sum=0;// 线段序列、线段条数和最小长度初始化// 点l..点n以y为第一关键字、x作为第二关键字的// 顺序排列；t = 1;// 当前水平线段的点数初始化为1for (i = 2; i <= n; ++i)// 由左而右搜索点2..n{if (p［i］.y != p［i - 1］.y)// 在i点为一条水平线段起点的情况下，若点数为奇数，// 则失败退出；否则当前水平线段的点数设为1{if (t % 2 != 0) return false;t = 1;}Else// i点与i-1点同属一条水平线段，水平线段的点数+1。// 若点数为偶数，则添加一条连接i点与i-1点的线段，累计线段总长度，记下线段的序号和两个端点{if ((++t) % 2 == 0){sum += sum ［i］.x-p［i-1］.x;s［++m］.p1 = p［i-1］; s［m］.p2=p［i］;pos［p［i］.id］［++pos［p［i］.id］［0］］=m;pos［p［i-1］.id］［++pos［p［i-1］.id］［0］］=m;e［p［i］.id］［++e［p［i］.id］［0］］=p［i-1］.id;e［p［i-1］.id］［++e［p［i-1］.id］［0］］=p［i］.id;}}}if (t % 2 != 0) return false;// 若当前水平线段的点数为奇数，则失败退出// 点l..点n以x为第一关键字、y作为第二关键字的// 顺序排列t = 1;// 当前垂直线段的点数初始化为1for (i = 2; i <= n; ++i)// 由上而下搜索点2..n{if (p［i］.x != p［i - 1］.x)// 在i点为一条垂直线段起点的情况下，若点数为奇数，// 则失败退出；否则当前垂直线段的点数设为1{if (t % 2 != 0) return false;t=1;}else// i点与i-1点属同一条垂直线段。当前垂直线段的点数// +1。若点数为偶数，则添加一条连接i点与i-1点的垂直线段。累计线段总长度，记下线段的序号和两个端点{if ((++t) % 2 == 0) {sum += p［i］.y-p［i-1］.y;s［++m］.p1=p［i-1］;s［m］.p2=p［i］;pos［p［i］.id］［++pos［p［i］.id］［0］］ = m;pos［p［i-1］.id］［++pos［p［i-1］.id］［0］］=m;e［p［i］.id］［++e［p［i］.id］［0］］=p［i-1］.id;e［p［i-1］.id］［++e［p［i-1］.id］［0］］=p［i］.id;}}}if(t%2!=0)return false;// 若当前垂直线段的点数为奇数，则失败退出否则成功// 退出return true;}
void find(int i)// 从点1出发,递归计算连通的点数k{++k; f［i］ = true;// 累计访问的点数,访问点iif (! f［e［i］［1］］) find(e［i］［1］);// 若连接点i的第1条线段的另一端点未访问,则访问该点；// 否则若连接点i的第2条线段的另一端点未访问,则访问该点else{if (!f［e［i］［2］］) find(e［i］［2］);}}
bool Check1()// 返回所有线段是否连通的标志{k=0;memset(f,0, sizeof(f));// 访问的点数和访问标志初始化find(1);// 从点1出发递归计算连通的点数kif (k != n)return false;// 若连通的点数不足n,则返回false；否则返回true else return true;}
int cal(int x)// 在a数组中二分查找值为x的元素下标{int i, j, mid;i=1;j=t;// 左右指针初始化while (i != j)// 若区间存在,则计算中间指针{mid = (i + j) / 2;if (a［mid］ == x) { i=mid;break; };// 若中间元素值为x,则返回其下标if (x}return i;// 返回a数组中值为x的元素下标}
void tree_ins(int i,int s,int t,int k,int x)// 线段树中事件点i对应的区间为［s,t］。将其子树中// 事件点k对应的子区间增加x个点{int mid;if (s==t) { tree［i］ += tree［i］;return; }// 若找到事件点k，则对应的子区间增加x个点，并返回mid = (s+t) / 2;// 计算区间的中间指针，根据事件点k所在的子区间递归// 左子树或右子树if (k <= mid) tree_ins(2*i,s,mid,k,x);else tree_ins(2*i+1,mid+1,t,k,x);tree［i］ = tree［2i］ + tree［2i+1］;// 累计事件点i对应区间的点数}
int tree_check(int i,int s,int t,int s1,int t1)// 线段树中事件点i对应的区间为［s,t］，查找其子树区间// ［s1，t1］的点数{int mid;if((s==s1)&&(t==t1))return tree［i］;// 若找到子树区间［s1，t1］，则返回区间内的点数mid = (s+t) / 2;// 计算区间的中间指针，分三种情形（［s1，t1］在左子树、// 在右子树、横跨左右子树）递归if (t1<=mid) return tree_check(2*i,s,mid,s1,t1);if (s1>mid) return tree_check(2*i+1,mid+1,t,s1,t1);return tree_check(2i,s,mid,s1,mid)+tree_check(2i+1,mid+1,t,mid+1,t1);}
bool Check2()// 若出现线段自交的情况，则返回false；否则返回true{int i, j;int l, k1, k2;for (i=1;i<=n;++i)aa［i］=p［i］.y;// 点l..点n按照y坐标值递增的顺序建立事件序列at=1; a［1］ = aa［1］;for (i = 2; i <= n; ++i) if (aa［i］ != aa［i-1］) a［++t］=aa［i］;memset(tree, 0, sizeof(tree));// 线段树为空for (i = 1; i <= n; ++i)// 枚举每个点连接的所有边{for (j = 1; j <= pos［p［i］.id］［0］; ++j){l = pos［p［i］.id］［j］;// 计算连接点i的第j条边的序号lif(s［l］.p1.x==s［l］.p2.x)// 若边l为垂直线段，则计算两端y坐标值对应的事件点// k1和k2{k1 = cal(s［l］.p1.y); k2 = cal(s［l］.p2.y);if ((k1+1<=k2-1)%(tree_check(1,1,t,k1+1,k2-1)!=0))// 在线段树中查找［k1+1，k2-1］。若区间内有点存在，// 说明存在与线段l相交的线段，返回线段自交标志 return false;}else{k1 = cal(s［l］.p1.y);// 边l为水平线段。计算边l的p1端的y值对应a序列// 的事件点k1。若点i为边l的左端点，则对应的事件点k1插入y轴区间的线段树中；若点i为边l的右端点，// 则对应的事件点k1从y轴区间的线段树中删除if (p［i］.x == s［l］.p1.x) tree_ins(1,1,t,k1,1) ;else tree_ins(1,1,t,k1,-1);}}}return true;// 返回所有线段不自交标志}
void Make()// 若线段满足要求，则输出最小长度；否则输出无解信息{if(! Succ()){ cout<< "-1"<< endl;return;}// 若存在线段不衔接情况，则失败退出if(! Check1()){ cout<< "-1"<if(! Check2()){ cout<<"-1"<cout << sum << endl;// 输出最小长度和}
int main(){Init();// 输入信息Make();// 若线段满足要求，则输出最小长度；否则输出无解信息return 0;}
【1.3.2 LCIS】 【问题描述】 给出n个整数，有两种操作： 1) U A B：用B取代第A个数(下标从0开始计数)。 2) Q A B：输出在［A，B］中最长连续递增子序列(the Longest Consecutive Increasing Subsequence，LCIS)的长度。 输入： 在第一行给出T，表示测试用例的个数。每个测试用例的开始给出两个整数n、m(0<n，m≤105)。下一行给出n个整数(0≤val≤105)。接下来的m行每行给出一个操作：U A B(0≤A<n，0≤B≤105)或Q A B(0≤A≤B<n)。 输出： <div style="text-align: center"> <img src=" https://yqfile.alicdn.com/027fce1d4a259f7d1a2fc674b203a9d3998ed309.png" > </div> 试题解析 简述题意：给出一个序列，两种操作：单点更新值和查询区间的最长连续递增子序列长度。 这是一个典型的区间合并问题，每一个节点(节点代表区间的长度为len)需要记录3个域信息： 1) 包含左端点的最长连续递增子长度lsum。 2) 包含右端点的最长连续递增子长度rsum。 3) 整个区间的最长递增子长度Msum。 无论是单点更新还是构造线段数，都需要自下而上更新，即把儿子的3个域信息上传给父节点，并对父节点的3个域信息进行更新。向上更新就是区间合并。 对于左连续，既可以由左孩子的左连续得来，也可能包括右孩子的左连续，要判断左孩子的左连续是否是整个区间，而且中间的结合是否满足递增。右连续亦一样。 对于整个区间的最值，可能来源于左右孩子的最值，也可以来源于两个区间的中间部分。 1) 若左儿子最右边的值<右儿子最左边的值，则节点的3个域调整如下：lsum=(左儿子的lsum==左儿子的len)？左儿子的len+右儿子的lsum：左儿子的lsum;rsum=(右儿子的rsum==右儿子的len)？右儿子的len+左儿子的rsum：右儿子的rsum;Msum=max{ 左儿子的rsum+右儿子的lsum，左儿子的Msum，右儿子的Msum，lsum，rsum);
2) 左儿子最右边的值≥右儿子最左边的值，则节点的3个域调整如下：lsum=左儿子的lsum；rsum=右儿子的rsum；Msum=max{左儿子的Msum，右儿子的Msum};
查找区间［l，r］中最长递增子序列的长度也需十分小心。查找过程从根出发，自上而下查找。 设当前节点p代表区间的中间指针是mid=p.l+p.r2」。若r≤mid，则递归左儿子p.l；若l>mid；则递归右儿子p.r；否则说明［l，r］横跨p的左右儿子。LCIS［l，r］=max{ 左儿子的LCIS［l，mid］，右儿子的LCIS［mid+1，r］， 左儿子的LCIS［l，mid］+右儿子的LCIS［mid+1，r］│左儿子右端数据与右儿子左端数据满足递增要求 }查找过程一直进行到［p.l，p.r］==［l，r］为止。p节点的Msum即为查询结果。 程序清单using namespace std;constint MSUMN=100005; struct node// 线段树节点的结构定义{int l,r;// 代表区间［l,r］int msum;// 整个区间的最长递增子序列长度为msum，其中左端最长连续// 递增子长度为lsum、右端最长连续递增子序列长度为rsum int lsum,rsum; int mid()// 计算区间［l,r］的中间指针{return (l+r)>>1;}};node tree［MSUMN*4］;// 线段树int num［MSUMN］;// 序列inline void pushup(int pos)// 上传左右儿子信息，调整pos节点的3个域{tree［pos］.msum=msum(tree［lson］.msum,tree［rson］.msum);// 上传左右儿子信息tree［pos］.lsum=tree［lson］.lsum;tree［pos］.rsum=tree［rson］.rsum;if(num［tree［lson］.r］// 若左儿子右端数字小于右儿子左端数字，则合并左右儿子{tree［pos］.msum=msum(tree［pos］.msum,tree［lson］.rsum+tree［rson］.lsum);if(tree［lson］.lsum==tree［lson］.r-tree［lson］.l+1)// 左子区间满足递增要求tree［pos］.lsum+=tree［rson］.lsum;if(tree［rson］.rsum==tree［rson］.r-tree［rson］.l+1)// 右子区间满足递增要求tree［pos］.rsum+=tree［lson］.rsum;}}
void build(int l,int r,int pos)// 构建以pos节点为根、代表区间［l,r］的线段树{tree［pos］.l=l;tree［pos］.r=r;// 设定节点pos的左右指针if(l==r)// 若节点pos为叶子,则左端最长连续递增子长度、右端的最长// 连续递增子长度，以及整个区间的最长递增子长度为1，返回 {tree［pos］.lsum=tree［pos］.rsum=tree［pos］.msum=1;return ;}int mid=tree［pos］.mid();// 计算pos代表区间的中间指针build(l,mid,lson);build(mid+1,r,rson);// 递归pos的左右子树pushup(pos);// 上传左右儿子信息，调整pos的3个域}
Void update(int a,int b,int pos)// 从节点pos出发，单点更新将num［a］的值改为b{if(tree［pos］.l==tree［pos］.r)// 找到位置，该值并返回 { num［a］=b; return ;}int mid=tree［pos］.mid();// 计算pos代表区间的中间指if(a<=mid) update(a,b,lson);// 更新位置在左区间，则递归左儿子；否则递归右儿子else update(a,b,rson);pushup(pos);// 上传左右儿子信息，调整pos节点的3个域}
int queryL(int l,int r,int pos)// 检查pos节点左端最长递增子序列的长度：若不超过待查区间// ［l，r］的长度，则返回左端最长递增子序列的长度；否则返回［l，r］的长度{if(r-l+1>=tree［pos］.lsum)return tree［pos］.lsum;else return r-l+1;}
int queryR(int l,int r,int pos)// 检查pos节点右端最长递增子序列的长度：若不超过待查区间// ［l，r］的长度，则返回右端最长递增子序列的长度；否则返回［l，r］的长度{if(r-l+1>=tree［pos］.rsum) return tree［pos］.rsum;else return r-l+1;}
int query(int l,int r,int pos)// 从节点pos出发，查找区间［l,r］中最长递增子序列的长度{if(l==tree［pos］.l&&r==tree［pos］.r)return tree［pos］.msum;// 若pos节点恰为待查区间，则返回pos节点的最长递增子序列长度int mid=tree［pos］.mid();// 计算pos节点的中间指针if(r<=mid)return query(l,r,lson);// 若pos的左儿子含待查区间，则递归左儿子；若pos的右儿子// 含待查区间，则递归右儿子else if(l>mid)return query(l,r,rson);else// 待查区间［l,r］横跨pos的左右儿子。LCIS［l,r］=max{左// 儿子的LCIS［l,mid］，右儿子的LCIS［mid+1,r］,左儿子的LCIS［l,mid］+右儿子的LCIS［mid+1,r］,│左儿子右端数据// 与右儿子左端数据满足递增要求}{int res=0;if(num［tree［lson］.r］res=msum(res,queryR(l,mid,lson)+queryL(mid+1,r,rson));res=msum(res,query(l,mid,lson));res=msum(res,query(mid+1,r,rson));return res;}}
int main(){int n,m,t;scanf("%d",&t);// 输入测试用例数while(t--)// 依次处理每个测试用例{scanf("%d%d",&n,&m);// 输入序列长度和命令数int i;for(i=1;i<=n;i++)// 输入序列scanf("%d",&num［i］);build(1,n,1);// 构建线段树char word［2］;// 命令字for(i=1;i<=m;i++)// 依次处理命令{int a,b;scanf("%s%d%d",word,&a,&b);// 输入命令字和参数 if(word［0］=='U')update(a+1,b,1);// 若单点更新命令，则将num［a+1］的值改为belse// 查询命令{int x=query(a+1,b+1,1);// 计算和输出num［a+1］..num［b+1］区间中最长连续递增// 子序列的长度printf("%d＼n",x);}}}return 0;}
我们在本节给出的线段树是一维的，即仅介绍了利用线段树处理简单的几何线段或数据区间的一般方法。实际上线段树的拓展性很广：例如线段树既可以处理线段问题，也可以转化为对数据点的操作，因为数据点也可以被理解为特殊的区间；另外，虽然一维线段树便于线性统计，但亦可以拓展为二维线段树和多维线段树，用于平面统计和空间统计。有关这方面的知识，我们将在第4章中专门阐释。 相关资源：七夕情人节表白HTML源码(两款)