数据结构杂谈

· · 个人记录

结束之前总想写点什么，就在这里胡言乱语几句吧。

分块一大优美之处是复杂度可以摊。就比如在很多情况下，修改和查询可以其中一个根号，另外一个为 O(1)。这样就可以进行莫队套分块，分块套分块之类的操作，从而保证总复杂度依旧为根号。当然不仅如此，B^2，T^2 之类的东西也可以和其他的均摊来得到更优复杂度。

线段树要维护信息本身、信息上传（合并）、信息下传（分裂），然后显式建出分治树，并在树上进行操作。分块就简单很多，每次区间操作只需要把区间拆成若干小段然后分别处理即可。线段树是多层结构，而分块只需要拆为一层。

分块也有很多技巧。举个例子，块内离散化。一个块内只有 B 个元素，离散化后元素总数是 O(B)，这样就可以存下「两两之间」的信息，每个块只需要 O(B^2) 的存储开销，总复杂度也是单根号的。块内离散化能应对单点加、单点赋值、区间加、区间推平、区间替换等操作。这种做法要把经常循环的维放在最后，从而降低常数。

分块通常作为非正解出现，所以尤其注意卡常。通常的卡常技巧有，寻址连续、手写 bitset、vector 换普通数组、去掉 #define int long long、删除不必要操作、去除不必要块内重构。一定要先保证正确性再卡常，卡常过程中时刻注意正确性。

姑且认为定期重构也是分块，对时间维的分块。定期重构有一些非常好的性质，比如可以做 ddp。对时间维分块，每个块内就有 O(B) 个树上修改查询。操作完一个块就对整棵树重构，所以只需要处理块内即可。对于块内的操作节点，建出虚树，点数为 O(B)，然后处理出虚树上每个点到父亲的转移矩阵，因为虚树，所以没有其他修改干扰。对于每个修改查询，直接暴力跳到根即可。

分块的优势在于单层结构，所有块都是在同一层的，也就是不需要处理层与层之间的关系。若需要多个块顺序合并若干非 O(1) 的信息，可以考虑把信息下放到每个块预处理。

分块的功能性也很强大，其他数据结构大多数对于一个结构最多存线性的信息。但是分块不一样，在单根号的情况，一个块内能存 O(B^2) 的信息，甚至能在两两块之间存 O(B) 的信息。这样的情况要尤为注意常数，减少不必要的数组可以使常数减半。

分块重要的是转化技巧以及卡常技巧，有时间再展开说。

接下来说线段树。线段树要看本质，显式建出分治树，然后树上的每个点存储子树内所有点合并后的信息。

树套树就是利用这一点，每个点上开一棵线段树。一个叶子影响的点只有其到根路径上的 O(\log) 个点，直接暴力跳复杂度就是对的。

线段树建图也是利用这个性质，把区间拆分为分治树上的 O(\log) 个区间，也就是树上结点。

线段树分治和线段树建图类似，把修改的生效时间作为区间挂到分治树上。在分治树上跳，进入一个点操作，从一个点出去撤销，从而动态维护当前状态。这样的形态就能做删除困难但撤销最后一次插入容易的操作。

常规线段树操作即为对分治树操作。一个点的作用范围是其到根的路径，一个区间被拆分为分治树上 O(\log) 个点。线段树信息传递依赖于二叉结构，父亲-左儿子-右儿子信息上下传，在操作树上维护这个过程，就是线段树。

线段树的延迟标记，处理时对应下传标记。思想是把标记累计，要用的时候再处理。而每次操作影响的点数为 O(\log) 的，所以复杂度是对的。这样需要标记的可加性，而矩阵恰恰满足这个性质，所以可以用线段树维护矩阵。

首先我们有全局的线段树二分。从根开始遍历，如果满足要求就减去左子树影响，然后走右子树；否则直接走左子树。对于区间线段树二分，可以按照上面的思路，把区间拆分成分治树上若干个点，从前到后遍历每个点，如果合法减去影响走下一个，否则就直接对这个点启动线段树二分。

树状数组就像手写签字笔，中重型数据结构就像电脑上绘图软件。签字笔的优势为小巧、高速，比如画张草图、简单运算的都可以用笔在纸上进行演算，单点修改区间查询、区间修改单点查询类就可以直接使用树状数组。而更复杂的情况，比如若干个圆求交点，这个时候需要借助圆规等仪器，就不如直接启动绘图软件了。就比如区间修改区间查询通常就使用线段树了。