分块套树状数组

简介

分块套树状数组在特定条件下可以用来做一些树套树可以做的事情，但是相比起树套树，分块套树状数组代码编写更加简短，更加容易实现。

简单的例子

一个简单的例子就是二维平面中矩阵区域内点数的查询。

对于操作 1，可以通过矩形容斥将其转化为 4 个二维偏序的查询去解决，然后因为强制在线，CDQ 分治之类的离线算法就解决不了，于是想到了树套树，比如树状数组套 Treap。这确实可以解决这个问题，但是代码太长了，也不是特别好实现。

注意到，题目还额外保证了 ，这个时候就可以用分块套树状数组解决。

初始化

首先，一个 只对应一个 ，所以可以用一个数组记录这个映射关系，比如令 表示横坐标为 的点的纵坐标。

然后，以 为块大小对横坐标进行分块。为每个块建一棵权值树状数组。记 为第 个块对应的树状数组， 表示块 里纵坐标在 内的点的个数。

查询

对于操作 1，将其转化为 4 个二维偏序的查询。现在只需要解决给出 ，询问有多少个点满足 。

现在要查询横坐标的范围为 。因为查询范围最右边可能有一段不是完整的块，所以暴力扫一遍这个段，看是否满足 ，统计出这个段满足要求的点的个数。

现在就只需要处理完整的块。暴力扫一遍前面的块，查询每个块对应的树状数组中值小于 的个数，累加到答案上。

这就完事了？不，注意到处理完整的块的时候，其实相当于查询 的前缀和，如果修改时也使用树状数组的技巧处理 ，那么查询时复杂度会更低。

修改

普通的做法就先找到点 所在的块，然后一减一加两个权值树状数组单点修改，再将 置为 。

如果用了上面说的优化，那就是对 也走一个树状数组修改的流程，每次修改也是一减一加两个权值树状数组单点修改。

对上述步骤进行一定的改变，比如将一减一加改成只减，就是删点；改成只加，就是加点。但是必须要注意一个 只能对应一个 。

空间复杂度

分块分了 个块，每个块一颗线段树 的空间，所以空间复杂度为 。

时间复杂度

查询的话，遍历非完整块的段 。然后，对 走树状数组查询，每个经历到的 也走树状数组查询，这一步是 的复杂度。所以查询的时间复杂度为 。

修改和查询一样，复杂度为 。

例题 1

对于每个值 ，记 是它在排列 中的下标， 是它在排列 中的下标。这样，操作一就变成了一个矩形区域内点的个数的询问，操作 2 可以看成两个修改操作。而且因为是排列，所以满足一个 对应一个 ，所以这题可以用分块套树状数组来写。

例题 2

观察：一个序列的 MEX 为 ，当且仅当这个序列包含 至 ，但不包含 。

依次判断是否存在 MEX 为 至 的连续子序列。如果没有 MEX 为 的连续子序列，那么答案即为 。如果都存在，那么答案为 。

在判断 时，将序列视为由零或多个 分隔的多个段。如果存在一个段，这个段中包含 至 ，但不包含 ，那么就说明存在值为 的连续子序列。

用一个数组 记录上一个值为 的元素的位置，以 作为 ， 作为 ， 作为 。这样，计算段内是否包含 至 就是一个三维偏序的问题。形式化的说，判断段 的 MEX 值是否为 ，就是看满足 的点的个数是否为 。

如果在判断完值为 的元素之后再将对应的点插入，这时因为 内只存在 的元素，所以上述三维偏序问题就可以转换为二维偏序的问题。