#创人计划# 对【数据删除】的拙劣模仿
2025-07-20 11:35:59
发布于：北京
所以说我现在要模仿复仇者-帅同写一个非常神秘的创人计划，那么我要干什么呢，我需要仔细想想，我发现我现在已经开始遗忘前面说的话了。我刚才说“我需要仔细想想”，我要想什么呢，我说我已经开始遗忘前面的话了，需要仔细想想，但是我不知道我需要想什么，我似乎只会复读我前面的话。那么我可能需要学习一些复读以外的新技能，比如线段树。那么我就来讲一下线段树是什么吧。线段树是一种树形结构，用分治的思想维护一些区间问题，线段树的每个节点记录了区间的信息，然后递归地建树从而维护整个区间的信息。所以说线段树节点的两个儿子也是线段树。看起来我大概说了一下线段树的定义，我觉得可以从模板的线段树一开始讲解线段树的具体实现了。这题线段树需要实现区间加区间和，我们需要考虑线段树的每个节点维护什么东西。注意到线段树其实是在维护一个双半群信息，这涉及到群论的内容，但是不重要，我们可以使用广义矩阵乘法。广义矩阵乘法就是把矩阵乘法的加法和乘法改成最大和加法，广义矩阵乘法可以做一些难以实现的dp问题。例如带修树上最大独立集问题，正常我们可以使用dp，但是因为带修，我们不可以修改后再跑一次dp，所以我们需要使用ddp的技巧，也就是动态dp，动态dp一般是在树上的，我们可以把dp过程抽象为广义矩阵乘法然后用树剖线段树来维护区间矩阵乘，所以说我们需要讲一下线段树是什么。线段树的每个节点记录了区间的信息，线段树节点的儿子也是线段树，把儿子信息合并就可以计算出当前节点的信息了。那我觉得我刚才已经讲得足够清楚了，我们来讲一下吉司机树，祭司技术其实就是势能线段树，这涉及到势能分析。在谈论势能分析前，我们可以讲一下什么是珂朵莉树。珂朵莉树其实是一个弱于线段树和块状链表的东西，那么我们可以讲一下什么是块状链表。块状链表就是支持动态调整块长的序列分块，至于序列分块，我们引用BaiRX的一句话：分块是我爹。基于这种原因，我觉得我不需要再解释分块是什么，你只需要知道它是BaiRX的爹。但是块状链表是严格强于分块的，这个事情显然，因为你如果不想让它动态调整那你就不调，反正就是比分块厉害。如果说块状链表的每个节点内部信息有一定单调性，比如说它们的值都一样，这时候我们就有了一些有意思的性质。考虑这样一个问题：区间修改为v，区间和。这个问题我们就可以使用刚才所谓的单调块状链表实现（所以我是怎么想起来我刚才说了啥的？），我们只需要区间覆盖的时候把两端的块分裂，然后中间的合成为一段，再打个标记就可以实现修改，查询操作，我们可以对大块建立线段树，但是线段树好像是不可以动态插入删除的。其实是可以，但是我更建议写平衡树。那么你都写平衡树了为什么还要写块状链表呢？所以这是一个很魔怔的算法，这个算法就叫珂朵莉树。我们来分析一下刚才我们的时间复杂度，首先查询操作是很显然的单老哥，这就不用说了，关于平衡树复杂度的证明可以去看BaiRX发的创作计划。那么关键是区间覆盖的复杂度。注意到我们每暴力删除一个节点，节点就被暴力删除了一个，所以说单次覆盖的复杂度上限是欧恩的，但其实不然，因为你每次区间覆盖，至多增加两个节点，每个节点只会被删除一次，因为没有人能杀死鬼。所以说你的节点总量是不会超过欧爱慕个的，因此珂朵莉树处理区间覆盖区间和问题的总时间复杂度就是单老哥的。我们回顾一下刚才对珂朵莉树的时间复杂度分析，发现我们每次修改会增加欧伊个点，每删除欧伊个点需要欧老哥的时间复杂度，你可以把这里的点数当成所谓的势能函数，吉司机树就是使用一些看似暴力的操作，但经过势能分析后的均摊复杂度可以接受的线段树。我们来看吉司机树的模板题线段树三，但是这题有一个前置那就是CPU监控，CPU监控的前置是线段树二，线段树二的精髓就是关于标记的合并，你需要注意标记合并后应该还是一个标记，而不是用一个维克托存下所有的操作，这样你就踢飞了。CPU监控的重点就是考虑如何维护线段树的双半群模型，这里再解释一下：对于线段树的每个节点，你需要维护值和标记，值和值以及标记和标记有满足结合律的合并操作，同时标记对值有满足分配率的应用操作。比如说线段树一的值就是区间和和区间长度，标记就是区间加的量。值的合并以及标记的合并也是显然的，同时也满足分配律。对于CPU监控这道题目，我们的标记可以理解为对于这段区间的操作序列（其实所有线段树都是这样的）。我们还是先考虑值，只需要按照题意记录当前区间的最值和历史最值即可，对于值的合并比较的简单。对于标记，我们需要维护四个量：加法操作的总值和总值历史最值；覆盖操作的值和历史最值。引用某篇题解的一句话：我们可以把历史最值当成是操作序列前缀和的最值，所以对于标记的合并读者可以自己推导，然后再写一下标记对值的应用，就可以通过一道水紫。那么我们回到线段树三（那我现在又是怎么想起来的呢？），线段树三的前面几个操作，就是刚才我讲的线段树一和CPU监控的合并，我们来考虑一下加上区间对v取min以后要怎么办。如果我们待修改的区间只有一种数不小于v，那么修改是很简单的。我们只需要记录区间的最大值和最大值的数量，那么对于值的应用操作就比较好想了。但是我们待修改的区间又不止一种数不小于v，怎么办呢。我们可以记录一段区间的次大值，如果次大值比v小，是不是说明待修改区间只有一种数不小于v了，直接改即可。所以我们对于每一次的对v取min的操作，我们暴力地修改所有这样的区间，就可以保证正确性。我们的时间复杂度要如何计算呢，我们还是定义势能函数为线段树极长同值段的数量，每次加法操作会增加这个势能，每次对v取min操作耗时越大对势能的降低越大，所以这样的复杂度是两个老哥的。然后我们来讲一下线段树上二分，线段树上二分其实是一个比较好懂的算法，主要就是按照某个规则找到某个下标。所以说和一般的二分一样，你二分的这个部分是需要单调，而且依赖于线段树存储的值的，然后遍历整棵树，看看答案应该在左子树还是右子树，再递归下去，复杂度肯定是一个老哥。然后我们可以看线段树上二分的模板题叫冰火战士。这题你推完公式以后发现是在一个单峰函数上面找峰，如果二分再线段树复杂度是两个老哥，但是你直接线段树上二分就可以击败一个老哥了。但是呢，线段树的常数有点小大，你把这个东西改成树状数组就行了，关于树状数组，你可以认为它是重链剖分后的线段树，这样有助于你理解什么是树状数组上二分。真的有助于吗？其实我也不太知道，但是你如果可以耐心地看到这我相信你应该有理解树状数组上二分的能力。但是线段树还远远没讲完。首先我讲一下什么是动态开点线段树，但是感觉不用讲，我们来讲可持久化线段树。可持久化数据结构需要支持对历史版本的保留，那么可持久化线段树是什么样的呢？你首先有一个动态开点的线段树，然后单点修改的时候，肯定只会修改欧老哥个点，那么剩下欧恩个点是不是不用修改。这个时候如果你为了保留当前的版本而重新建树，看起来就唐唐的。所以如果一个节点的一个儿子没被修改，我们就把它向这个儿子的边连向之前的某个历史版本的这个儿子，就可以实现欧老哥的修改。具体来说，修改的时候我们每递归到一个点，就复制一遍，这样就可以保存儿子的信息等，然后再对复制出来的新节点进行修改操作，这样就能保证不对历史版本造成影响。如果一个线段树有朴实宕操作，那么它在朴实宕的时候也要复制新节点，但是这样看起来又假假的，所以需要一些标记永久化的技巧，但是我其实也不太会，怎么办呢？那我不是不配写这篇奇怪的东西了吗？没有关系！我可以讲一个可持久化线段树二用来水字数。这题是静态区间第k小问题。既然是静态区间查询，我们应该理所应当地想到前缀和，我们考虑一个神秘的暴力。考虑开n个set，第i个set里面放着前i个数，我们查询的时候二分答案，然后算出第l-1和第r个set里面有多少数比mid小，如果恰为k个，mid就是答案，这么干的时间复杂度有点小大，是双老哥恩方的。所以说我们可以不用set，使用可持久化的平衡树，查询的时候还是二分答案，所以说可以达到恩双老哥，但是还不够。平衡树是不支持整体二分的，但是线段树可以。所以说你把可持久化平衡树改成可持久化权值线段树，或者说是01trie树，就可以进行整体线段树上二分，成功击败一个老哥，时空复杂度都是双老哥的。在这道题目有两个限制，分别是查询区间和查询的k，静态两限制问题一般是对序列建立可持久化线段树，但是如果带修了，我们就不可以同时修改欧恩个线段树版本，这个时候我们需要使用树套树。树套树，我们一般选择树状数组套权值线段树，树状数组的第i个节点相当于对(i^lowbit(i),i]这段区间建立权值线段树，当然你要动态开点要不然空间开不下。这样的话你的各种操作都可以在两个老哥以内完成，注意查询第k小的时候需要使用整体线段树二分的技巧，就可以砍死一个老哥，这是线段树相比于平衡树的优势。所以一般来说，静态双限制问题可以使用可持久化线段树，而动态双限制问题可以使用树套树。我们再看看三维偏序的这道题，静态三限制问题，自然想到通过排序砍掉一个限制，然后转化为动态双限制问题并用树套树求解。而如果你想要把动态问题转化为静态问题，只需要离线下来，然后加入新的时间轴限制即可。所以说我们得到了一个普遍的规律：当你每使用高一级的数据结构时，都可以消去需要你解决的某一维的限制。从前缀和差分到线段树，从可持久化线段树到树套树，实际上是在一步步消去这样的限制。扫描线，莫队，带修莫队和K-Dtree的关系也是如此。
有帮助，赞一个