1. 线段树组合技区间更新与二分查找的实战拆解线段树这个数据结构写过算法题的人都不陌生。但真正把线段树用出花来的往往不是那些只会套模板的人而是能把区间更新和二分查找、第k值查询这些操作组合起来解决复杂问题的人。今天要聊的这道题就是线段树组合技的经典代表——它同时考察了区间更新、区间查询、二分查找和第k个值的判断是一道能把线段树理解深度直接拉满的好题。这道题的核心场景是这样的有一排花瓶编号从0到N-1初始都是空的。有两种操作第一种是往指定区间里插花如果遇到已经插了花的位置就跳过直到插满指定数量的花或者区间遍历完第二种是清空指定区间内的所有花并告诉你清掉了多少朵。听起来像模拟题对吧但数据量一大纯模拟必然超时这时候线段树就派上用场了。我第一次遇到这道题的时候第一反应是用数组暴力模拟结果提交直接超时。后来仔细分析了一下操作特性发现每次操作本质上是在做两件事快速找到区间内第一个空位或者第一个非空位以及快速统计区间内空位或花的数量。这两个需求恰好对应线段树的区间查询和二分查找能力。把这两个能力组合起来就能在O(logN)甚至O(log²N)的时间内完成每次操作。这道题适合谁看如果你已经掌握了线段树的基本操作——建树、单点更新、区间查询——但还不知道怎么把线段树和其他技巧结合起来解决更复杂的问题那这道题就是绝佳的进阶练习。如果你连线段树的基本原理都还不清楚建议先去补一下基础否则后面的内容可能会有些吃力。不过我会尽量把每个关键步骤都讲透让有一定基础的人都能跟上。2. 核心思路与方案选型为什么是线段树加二分2.1 暴力模拟为什么不行先说说最直观的暴力思路。对于插入操作从起始位置开始逐个检查遇到空位就插花直到插够数量或者到达区间末尾。对于清空操作遍历区间内每个位置统计并清空。这个思路的时间复杂度是O(N)每次操作总共M次操作总复杂度O(NM)。当N和M都达到10^5级别时运算量就是10^10妥妥超时。有人可能会想能不能用一些简单的数据结构优化比如用set维护空位的集合插入操作就是不断从set里取大于等于起始位置的最小值取一个删一个。这个思路确实能把插入操作优化到O(KlogN)K是实际插入的数量。但清空操作就麻烦了需要遍历区间内所有已占用的位置如果区间很大且花很多还是O(N)级别。而且set的常数不小实际跑起来未必比线段树快。所以我们需要一种数据结构能够同时高效地支持区间统计和区间修改并且还能支持在区间内快速定位第一个满足条件的位置。线段树恰好满足所有这些需求。2.2 线段树节点设计的关键决策线段树的每个节点需要维护什么信息这是设计的第一步。对于这道题最核心的信息是区间内空位的数量。为什么是空位而不是花的数量因为插入操作需要找空位清空操作需要统计花的数量。两者其实可以互相转换花的数量等于区间长度减去空位数量。所以只维护空位数量就够了。但仅仅维护空位数量还不够我们还需要一个懒标记来支持区间更新。这里的区间更新有两种把区间全部置为空清空操作或者把区间全部置为满插入操作中当确定整个区间都要插花时。懒标记用一个整数表示0表示无标记1表示置空2表示置满。为什么不用布尔值因为置空和置满是两种不同的操作需要区分。注意懒标记的下推顺序很重要。如果当前节点已经有标记新的标记会覆盖旧标记因为后发的操作会覆盖之前的操作结果。这一点在写pushdown函数时要特别注意。2.3 二分查找在线段树上的应用插入操作的核心难点在于给定起始位置L和需要插入的数量K找到第K个空位的位置。如果暴力找就是不断查询单点是否为空复杂度O(KlogN)K可能很大。但我们可以利用线段树的区间统计能力用二分查找来加速。具体做法是先查询区间[L, N-1]内空位的总数。如果总数为0说明插不了花直接返回。如果总数小于等于K说明从L开始到末尾的所有空位都能插上花最后一个空位的位置就是区间内第总数个空位。如果总数大于K说明只需要插K朵花我们需要找到从L开始的第K个空位的位置。怎么找第K个空位这就是经典的线段树上二分。从根节点开始先看左子节点的空位数量。如果左子节点的空位数量大于等于K说明第K个空位在左子树递归进入左子树否则K减去左子节点的空位数量递归进入右子树。这个过程是O(logN)的因为每次只需要进入一个子节点。清空操作相对简单直接查询区间内花的数量区间长度减去空位数量然后区间置空即可。查询和更新都是O(logN)。2.4 两种实现路线的对比这道题有两种常见的实现路线一种是区间更新加二分查找另一种是区间更新加第k个值判断。两者的区别在于插入操作中如何定位第K个空位。二分查找的思路是在区间[L, N-1]上做二分每次查询中间位置到L之间有多少个空位根据空位数量调整二分边界。这个思路的时间复杂度是O(log²N)因为每次二分需要O(logN)的区间查询。第k个值判断的思路是直接在线段树上递归查找第K个空位利用线段树的树形结构天然支持这种查找。时间复杂度是O(logN)比二分查找少一个log。两种思路都能AC但第k个值判断更优雅效率也更高。不过二分查找的思路更直观更容易想到。我建议两种都实现一遍加深理解。实际比赛中如果时间紧张二分查找的思路更容易快速写出来如果追求极致效率第k个值判断是更好的选择。3. 核心细节解析与实操要点3.1 线段树数组的大小计算线段树数组的大小是一个容易被忽视但很重要的细节。对于区间[0, N-1]线段树的节点数量最多是4N。为什么是4N而不是2N因为线段树是一棵完全二叉树但叶子节点不一定都在同一层。对于长度为N的区间线段树的深度是logN向上取整节点总数最多是2的深度1次方减1。当N不是2的幂时这个值可能接近4N。所以保险起见数组开4N大小。具体来说如果N10^54N4×10^5这个大小完全没问题。但如果N10^64N4×10^6内存可能会比较紧张。不过这道题的N最大是10^5所以4N足够了。实操心得我习惯在开数组的时候多开一点比如4N10防止边界情况越界。这个习惯在写线段树的时候特别有用因为递归建树的时候可能会访问到稍微超出范围的索引。3.2 懒标记的下推时机与实现懒标记的下推是线段树区间更新的核心。什么时候需要下推当你需要访问一个节点的子节点时如果该节点有懒标记就必须先把标记下推给子节点否则子节点的信息是过时的。下推的实现需要注意几点。首先标记的类型要正确传递。如果父节点是置空标记子节点也应该被置空如果父节点是置满标记子节点也应该被置满。其次下推后父节点的标记要清除。最后子节点的空位数量要根据标记类型更新置空则空位数量等于区间长度置满则空位数量等于0。void pushDown(int node, int l, int r) { if (lazy[node] ! 0) { int mid (l r) / 2; int leftChild node * 2; int rightChild node * 2 1; if (lazy[node] 1) { // 置空 tree[leftChild] mid - l 1; tree[rightChild] r - mid; lazy[leftChild] 1; lazy[rightChild] 1; } else if (lazy[node] 2) { // 置满 tree[leftChild] 0; tree[rightChild] 0; lazy[leftChild] 2; lazy[rightChild] 2; } lazy[node] 0; } }这段代码看起来简单但有一个容易出错的地方当l等于r时也就是叶子节点不应该执行下推操作因为没有子节点。所以在调用pushDown之前要先判断l是否小于r。3.3 区间查询的写法细节区间查询的目的是统计某个区间内的空位数量。标准的线段树区间查询是递归实现的如果当前节点区间完全被查询区间包含直接返回节点值如果有部分重叠下推标记后递归查询左右子节点合并结果。这里有一个细节查询的时候要不要下推标记答案是肯定的。因为如果不下推子节点的信息可能是过时的查询结果就不准确。但下推标记会修改子节点的信息这会不会影响后续操作不会因为下推只是把父节点的标记传递给子节点逻辑上是一致的。int query(int node, int l, int r, int ql, int qr) { if (ql l r qr) { return tree[node]; } if (l r) pushDown(node, l, r); int mid (l r) / 2; int sum 0; if (ql mid) sum query(node * 2, l, mid, ql, qr); if (qr mid) sum query(node * 2 1, mid 1, r, ql, qr); return sum; }注意查询区间和节点区间没有重叠的情况不需要单独判断因为递归的边界条件已经保证了只在有重叠时才进入递归。但为了代码清晰也可以加上无重叠的判断。3.4 第k个空位的查找实现第k个空位的查找是这道题最核心的操作。给定起始位置L和需要找的第K个空位我们需要在区间[L, N-1]内找到第K个空位的位置。实现思路是这样的先查询区间[L, N-1]内的空位总数total。如果total小于K说明空位不够返回-1。否则我们需要找到从L开始的第K个空位。注意这里的“从L开始”意味着我们要在[L, N-1]这个区间内找第K个空位而不是在整个[0, N-1]内找。一种实现方式是先查询[0, L-1]内的空位数量before然后在整个线段树上找第before K个空位。这个思路是可行的但需要额外一次查询。另一种方式是直接写一个在指定区间内找第K个空位的函数递归时带上区间限制。int findKth(int node, int l, int r, int ql, int k) { if (l r) return l; if (l r) pushDown(node, l, r); int mid (l r) / 2; int leftChild node * 2; // 计算左子节点在查询区间内的空位数量 int leftCount 0; if (ql mid) { int queryL max(ql, l); int queryR mid; leftCount query(leftChild, l, mid, queryL, queryR); } if (leftCount k) { return findKth(leftChild, l, mid, ql, k); } else { return findKth(rightChild, mid 1, r, ql, k - leftCount); } }这个实现有一个小问题每次递归都要调用query函数导致复杂度变成O(log²N)。如果要做到O(logN)需要在递归过程中直接利用节点的空位数量而不是重新查询。但那样需要更复杂的边界处理。对于这道题的数据量O(log²N)已经足够了。4. 完整实操流程与代码实现4.1 建树与初始化建树的目的是初始化线段树把所有节点的空位数量设为区间长度懒标记设为0。递归建树的过程很简单但要注意叶子节点的处理。void build(int node, int l, int r) { lazy[node] 0; tree[node] r - l 1; // 初始全部为空 if (l r) return; int mid (l r) / 2; build(node * 2, l, mid); build(node * 2 1, mid 1, r); }建树的时间复杂度是O(N)因为每个节点访问一次。空间复杂度是O(N)因为线段树有O(N)个节点。4.2 区间更新置空与置满区间更新是线段树的核心操作之一。对于这道题有两种更新置空和置满。置空用于清空操作置满用于插入操作中确定整个区间都要插花的情况。void update(int node, int l, int r, int ul, int ur, int val) { if (ul l r ur) { if (val 1) { // 置空 tree[node] r - l 1; } else { // 置满 tree[node] 0; } lazy[node] val; return; } if (l r) pushDown(node, l, r); int mid (l r) / 2; if (ul mid) update(node * 2, l, mid, ul, ur, val); if (ur mid) update(node * 2 1, mid 1, r, ul, ur, val); tree[node] tree[node * 2] tree[node * 2 1]; }更新操作的复杂度是O(logN)因为每次最多访问O(logN)个节点。懒标记的引入使得区间更新不需要访问所有叶子节点大大提高了效率。4.3 插入操作的完整流程插入操作是这道题最复杂的部分。给定起始位置L和需要插入的数量K我们需要找到从L开始的第K个空位的位置然后把这个区间置满。void insert(int L, int K) { // 查询[L, N-1]内的空位总数 int total query(1, 0, N - 1, L, N - 1); if (total 0) { printf(Can not put any one.\n); return; } int actualK min(K, total); // 实际能插入的数量 // 找到从L开始的第actualK个空位的位置 int endPos findKth(1, 0, N - 1, L, actualK); // 找到从L开始的第1个空位的位置 int startPos findKth(1, 0, N - 1, L, 1); // 把[startPos, endPos]置满 update(1, 0, N - 1, startPos, endPos, 2); printf(%d %d\n, startPos, endPos); }这里有一个细节startPos和endPos的查找。startPos是从L开始的第1个空位endPos是从L开始的第actualK个空位。两者之间的所有位置不一定都是空位但根据插入规则我们会跳过已占用的位置所以实际插入的花的位置就是startPos到endPos之间的所有空位。把整个区间置满效果就是把这些空位都插上花已占用的位置保持不变因为置满操作会把整个区间都设为满但已占用的位置本来就是满的所以不影响。实操心得我一开始担心把整个区间置满会覆盖掉已占用的位置但仔细想想已占用的位置本来就是满的置满操作不会改变它们的状态。所以这个做法是正确的。4.4 清空操作的完整流程清空操作相对简单查询区间[L, R]内的花的数量然后把这个区间置空。void clear(int L, int R) { int emptyCount query(1, 0, N - 1, L, R); int flowerCount (R - L 1) - emptyCount; update(1, 0, N - 1, L, R, 1); // 置空 printf(%d\n, flowerCount); }清空操作的复杂度是O(logN)因为查询和更新都是O(logN)。4.5 主函数与输入输出处理主函数负责读取输入、处理操作、输出结果。这道题的输入格式是第一行一个整数T表示测试用例数量每个测试用例第一行两个整数N和M表示花瓶数量和操作数量接下来M行每行三个整数第一个整数表示操作类型1表示插入2表示清空后两个整数是操作参数。int main() { int T; scanf(%d, T); while (T--) { int N, M; scanf(%d%d, N, M); build(1, 0, N - 1); while (M--) { int op, a, b; scanf(%d%d%d, op, a, b); if (op 1) { insert(a, b); } else { clear(a, b); } } printf(\n); } return 0; }注意每个测试用例结束后要输出一个空行这是题目要求的格式。我一开始忘了这个空行结果Presentation Error了好几次。5. 常见问题与排查技巧实录5.1 懒标记下推遗漏导致的错误懒标记下推遗漏是线段树最常见的错误之一。症状是查询结果不正确或者更新后查询结果没有变化。原因是在访问子节点之前没有下推父节点的标记。排查方法检查所有需要访问子节点的地方包括查询、更新、查找第k个空位。确保在递归进入子节点之前都调用了pushDown。特别是findKth函数很容易忘记下推标记。避坑技巧我习惯在写线段树的时候把pushDown调用放在递归函数的最前面紧跟在边界判断之后。这样就不会遗漏。5.2 边界条件处理不当边界条件处理不当是另一个常见错误。比如查询区间和节点区间没有重叠时应该返回0而不是继续递归。再比如更新区间完全覆盖节点区间时应该直接更新并返回而不是继续递归。排查方法仔细检查每个递归函数的边界条件。对于查询函数无重叠返回0完全覆盖返回节点值部分重叠递归。对于更新函数完全覆盖直接更新并返回部分重叠递归。对于findKth函数叶子节点直接返回位置非叶子节点根据左子节点的空位数量决定递归方向。5.3 第k个空位查找的起始位置问题第k个空位查找的起始位置问题是一个容易忽略的细节。题目要求从L开始找第K个空位而不是从0开始。如果直接在整个线段树上找第K个空位结果可能不对。排查方法在findKth函数中要带上查询区间的左边界ql。计算左子节点的空位数量时只计算查询区间内的部分。如果ql大于mid说明查询区间完全在右子节点左子节点的空位数量为0。5.4 多测试用例的初始化问题多测试用例的初始化问题是一个低级但致命的错误。如果每个测试用例之前没有重新建树上一个测试用例的数据会残留导致结果错误。排查方法在每个测试用例开始时调用build函数重新建树。build函数会把所有节点的空位数量设为区间长度懒标记设为0相当于重新初始化。5.5 常见问题速查表问题现象可能原因排查方法解决方案查询结果不正确懒标记未下推检查所有访问子节点的地方在递归前调用pushDown更新后查询无变化更新未正确合并检查更新函数的合并逻辑更新后重新计算父节点值第k个空位位置错误起始位置未限制检查findKth的ql参数在计算左子节点空位数时限制区间多测试用例结果错误未重新建树检查每个测试用例开始处调用build重新初始化数组越界线段树数组开小了检查数组大小开到4N10输出格式错误缺少空行检查输出格式每个测试用例后输出空行实操心得这道题我前前后后提交了七八次才AC踩过的坑包括懒标记下推遗漏、第k个空位起始位置错误、多测试用例未重新建树等。每次调试的时候我都会把线段树的每个节点的状态打印出来对比预期值和实际值这样能快速定位问题。6. 性能优化与进阶思考6.1 时间复杂度分析这道题的时间复杂度取决于实现方式。如果使用二分查找加区间查询的方式找第k个空位每次插入操作的复杂度是O(log²N)清空操作是O(logN)。总复杂度是O(Mlog²N)。如果使用第k个值判断的方式每次插入操作的复杂度是O(logN)总复杂度是O(MlogN)。对于N10^5M10^5的数据量O(Mlog²N)大约是10^5×17×17≈2.9×10^7次操作完全可以在1秒内跑完。O(MlogN)大约是10^5×17≈1.7×10^6次操作更快。所以两种方式都能AC但第k个值判断更优。6.2 空间复杂度分析线段树的空间复杂度是O(N)因为线段树有O(N)个节点。对于N10^54N4×10^5个节点每个节点存储一个整数大约需要1.6MB内存完全没问题。6.3 进阶思考能否用树状数组实现树状数组也支持区间查询和单点更新但不支持区间更新。如果要用树状数组实现这道题需要用差分树状数组或者其他技巧。但树状数组不支持区间置空和区间置满这种操作所以实现起来会比较麻烦。线段树是更自然的选择。6.4 进阶思考能否用平衡树实现平衡树比如Treap或Splay可以维护空位的集合插入操作就是不断取空位并删除清空操作就是遍历区间内的空位并重新插入。但清空操作的复杂度取决于区间内空位的数量最坏情况下是O(N)。所以平衡树的实现不如线段树稳定。6.5 进阶思考线段树的动态开点如果N非常大比如10^9线段树的数组开不下这时候可以用动态开点线段树。动态开点线段树不预先分配所有节点而是用到哪个节点就创建哪个节点。对于这道题N最大是10^5不需要动态开点。但如果N更大动态开点就是一个必要的技巧。实操心得动态开点线段树的实现比普通线段树复杂一些需要维护左右子节点的指针。但核心思路是一样的只是把数组索引换成了指针。如果遇到N很大的题目可以考虑用动态开点。7. 从这道题延伸出的通用解题框架7.1 线段树加二分的通用模式这道题展示了一个通用的解题模式当需要在区间内找到第k个满足条件的位置时可以用线段树维护区间内满足条件的元素数量然后在线段树上二分查找。这个模式可以应用到很多类似的题目中比如找第k个零、找第k个一、找第k个偶数等。关键点在于线段树的每个节点维护区间内满足条件的元素数量二分查找时根据左子节点的数量决定递归方向。这个模式的时间复杂度是O(logN)非常高效。7.2 区间更新加区间查询的通用模式这道题还展示了区间更新加区间查询的通用模式。线段树通过懒标记实现了O(logN)的区间更新和区间查询。这个模式是线段树最基础也是最常用的模式几乎所有的线段树题目都会用到。关键点在于懒标记的设计和下推。懒标记要能正确表示区间的状态下推时要正确更新子节点的信息。不同的题目需要设计不同的懒标记比如这道题的置空和置满再比如区间加、区间乘等。7.3 多操作组合的解题思路这道题组合了多种操作区间查询、区间更新、第k个值查找。解题的关键是把复杂操作拆解成基本操作的组合。比如插入操作拆解成查询空位总数、查找第k个空位、区间置满三个基本操作。清空操作拆解成查询花的数量、区间置空两个基本操作。这种拆解思路在解决复杂问题时非常有用。先把问题拆解成若干基本操作然后逐个实现基本操作最后组合起来解决问题。7.4 调试线段树的实用技巧调试线段树的时候最有效的方法是打印中间状态。可以在每次操作后打印线段树的每个节点的值对比预期值和实际值。也可以写一个暴力版本用小数据随机生成测试用例对比线段树版本和暴力版本的结果。我常用的调试方法是写一个printTree函数递归打印每个节点的区间、空位数量、懒标记。然后在关键操作前后调用这个函数观察状态变化。这个方法虽然笨但非常有效能快速定位问题。实操心得线段树的bug往往很隐蔽因为递归的调用栈很深出错的地方可能离症状很远。所以调试的时候要有耐心一步一步跟踪。我一般会先用小数据N10左右手动模拟确认逻辑正确后再用大数据测试性能。8. 代码模板与快速复用8.1 完整代码模板把这道题的代码整理成一个模板方便以后遇到类似题目时快速复用。模板包含了线段树的基本操作建树、下推、查询、更新、查找第k个值。#include cstdio #include algorithm using namespace std; const int MAXN 100005; int tree[MAXN * 4]; int lazy[MAXN * 4]; int N, M; void build(int node, int l, int r) { lazy[node] 0; tree[node] r - l 1; if (l r) return; int mid (l r) / 2; build(node * 2, l, mid); build(node * 2 1, mid 1, r); } void pushDown(int node, int l, int r) { if (lazy[node] ! 0) { int mid (l r) / 2; int lc node * 2, rc node * 2 1; if (lazy[node] 1) { tree[lc] mid - l 1; tree[rc] r - mid; lazy[lc] lazy[rc] 1; } else { tree[lc] tree[rc] 0; lazy[lc] lazy[rc] 2; } lazy[node] 0; } } void update(int node, int l, int r, int ul, int ur, int val) { if (ul l r ur) { tree[node] (val 1) ? (r - l 1) : 0; lazy[node] val; return; } if (l r) pushDown(node, l, r); int mid (l r) / 2; if (ul mid) update(node * 2, l, mid, ul, ur, val); if (ur mid) update(node * 2 1, mid 1, r, ul, ur, val); tree[node] tree[node * 2] tree[node * 2 1]; } int query(int node, int l, int r, int ql, int qr) { if (ql l r qr) return tree[node]; if (l r) pushDown(node, l, r); int mid (l r) / 2; int sum 0; if (ql mid) sum query(node * 2, l, mid, ql, qr); if (qr mid) sum query(node * 2 1, mid 1, r, ql, qr); return sum; } int findKth(int node, int l, int r, int ql, int k) { if (l r) return l; if (l r) pushDown(node, l, r); int mid (l r) / 2; int lc node * 2; int leftCount 0; if (ql mid) { int qL max(ql, l); leftCount query(lc, l, mid, qL, mid); } if (leftCount k) { return findKth(lc, l, mid, ql, k); } else { return findKth(node * 2 1, mid 1, r, ql, k - leftCount); } } void insert(int L, int K) { int total query(1, 0, N - 1, L, N - 1); if (total 0) { printf(Can not put any one.\n); return; } int actualK min(K, total); int startPos findKth(1, 0, N - 1, L, 1); int endPos findKth(1, 0, N - 1, L, actualK); update(1, 0, N - 1, startPos, endPos, 2); printf(%d %d\n, startPos, endPos); } void clear(int L, int R) { int emptyCount query(1, 0, N - 1, L, R); int flowerCount (R - L 1) - emptyCount; update(1, 0, N - 1, L, R, 1); printf(%d\n, flowerCount); } int main() { int T; scanf(%d, T); while (T--) { scanf(%d%d, N, M); build(1, 0, N - 1); while (M--) { int op, a, b; scanf(%d%d%d, op, a, b); if (op 1) insert(a, b); else clear(a, b); } printf(\n); } return 0; }8.2 模板的复用要点这个模板可以复用到很多类似的题目中。复用的要点是修改节点维护的信息、修改懒标记的含义、修改更新和查询的逻辑。比如如果题目要求区间加和区间求和只需要把懒标记改成加法标记更新时累加即可。注意复用模板的时候要仔细检查边界条件和初始化逻辑。不同的题目可能有不同的初始状态比如这道题初始全部为空但有些题目可能初始全部为满或者初始有特定值。8.3 常见变体题目这道题的变体很多比如把花瓶换成书架把插花换成放书把清空换成取书或者把操作改成区间翻转、区间染色等。核心思路是一样的用线段树维护区间状态用二分查找或第k个值判断定位目标位置。掌握了这道题再遇到类似的题目就能快速上手。关键是要理解线段树的核心原理而不是死记模板。理解了原理就能灵活应对各种变体。9. 个人实操体会与建议这道题我做了好几遍每次都有新的收获。第一遍做的时候我用了二分查找加区间查询的方式虽然AC了但复杂度是O(log²N)跑得比较慢。第二遍做的时候我改成了第k个值判断的方式复杂度降到O(logN)跑得飞快。第三遍做的时候我尝试用树状数组实现发现不太适合又回到了线段树。我的建议是先把一种方式写熟确保能AC然后再尝试另一种方式对比两者的优劣。这样既能保证比赛时能快速写出代码又能加深对线段树的理解。另外这道题的调试过程也让我学到了很多。线段树的bug往往很隐蔽需要耐心调试。我常用的方法是打印中间状态对比预期值和实际值。这个方法虽然笨但非常有效。最后分享一个小技巧写线段树的时候可以把每个函数的职责写清楚比如build负责建树pushDown负责下推query负责查询update负责更新findKth负责查找第k个值。这样代码结构清晰调试的时候也容易定位问题。如果函数职责混乱调试起来会很痛苦。这道题后续还可以这样扩展增加区间翻转操作或者增加查询区间内连续空位的最大长度。这些扩展都需要对线段树有更深的理解有兴趣的可以试试。