分块套树状数组

数据结构 / bit-in-block-array

本地源文件：docs/ds__bit-in-block-array.md

分块套树状数组

简介

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

简单的例子

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

矩形区域查询

给出 𝑛n 个二维平面中的点 (𝑥𝑖,𝑦𝑖)(xi,yi)，其中 1 ≤𝑖 ≤𝑛,1 ≤𝑥𝑖,𝑦𝑖 ≤𝑛,1 ≤𝑛 ≤1051≤i≤n,1≤xi,yi≤n,1≤n≤105, 要求实现以下中操作：

  1. 给出 𝑎,𝑏,𝑐,𝑑a,b,c,d，询问以 (𝑎,𝑏)(a,b) 为左上角，𝑐,𝑑c,d 为右下角的矩形区域内点的个数．
  2. 给出 𝑥,𝑦x,y，将横坐标为 𝑥x 的点的纵坐标改为 𝑦y．

题目 强制在线 ，保证 𝑥𝑖 ≠𝑥𝑗(1 ≤𝑖,𝑗 ≤𝑛,𝑖 ≠𝑗)xi≠xj(1≤i,j≤n,i≠j)．

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

注意到，题目还额外保证了 𝑥𝑖 ≠𝑥𝑗(1 ≤𝑖,𝑗 ≤𝑛,𝑖 ≠𝑗)xi≠xj(1≤i,j≤n,i≠j)，这个时候就可以用分块套树状数组解决．

初始化

首先，一个 𝑥x 只对应一个 𝑦y，所以可以用一个数组记录这个映射关系，比如令 𝑌𝑖Yi 表示横坐标为 𝑖i 的点的纵坐标．

然后，以 √𝑛n 为块大小对横坐标进行分块．为每个块建一棵权值树状数组．记 𝑇𝑖Ti 为第 𝑖i 个块对应的树状数组，𝑇𝑖,𝑗Ti,j 表示块 𝑖i 里纵坐标在 (𝑗 −𝑙𝑜𝑤𝑏𝑖𝑡(𝑗),𝑗](j−lowbit(j),j] 内的点的个数．

查询

对于操作 1，将其转化为 4 个二维偏序的查询．现在只需要解决给出 𝑎,𝑏a,b，询问有多少个点满足 1 ≤𝑥𝑖 ≤𝑎,1 ≤𝑦𝑖 ≤𝑏1≤xi≤a,1≤yi≤b．

现在要查询横坐标的范围为 [1,𝑎][1,a]．因为查询范围最右边可能有一段不是完整的块，所以暴力扫一遍这个段，看是否满足 𝑌𝑖 ≤𝑏Yi≤b，统计出这个段满足要求的点的个数．

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

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

修改

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

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

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

空间复杂度

分块分了 √𝑛n 个块，每个块一个树状数组 𝑂(𝑛)O(n) 的空间，所以空间复杂度为 𝑂(𝑛√𝑛)O(nn)．

时间复杂度

查询的话，遍历非完整块的段 𝑂(√𝑛)O(n)．然后，对 𝑇T 走树状数组查询，每个经历到的 𝑇𝑖Ti 也走树状数组查询，这一步是 𝑂(log⁡(√𝑛)log⁡𝑛)O(log⁡(n)log⁡n) 的复杂度．所以查询的时间复杂度为 𝑂(√𝑛 +log⁡(√𝑛)log⁡𝑛)O(n+log⁡(n)log⁡n)．

修改和查询一样，复杂度为 𝑂(√𝑛 +log⁡(√𝑛)log⁡𝑛)O(n+log⁡(n)log⁡n)．

例题 1

Intersection of Permutations

给出两个排列 𝑎a 和 𝑏b，要求实现以下两种操作：

  1. 给出 𝑙𝑎,𝑟𝑎,𝑙𝑏,𝑟𝑏la,ra,lb,rb，要求查询既出现在 𝑎[𝑙𝑎...𝑟𝑎]a[la...ra] 又出现在 𝑏[𝑙𝑏...𝑟𝑏]b[lb...rb] 中的元素的个数．
  2. 给出 𝑥,𝑦x,y，𝑠𝑤𝑎𝑝(𝑏𝑥,𝑏𝑦)swap(bx,by)．

序列长度 𝑛n 满足 2 ≤𝑛 ≤2 ⋅1052≤n≤2⋅105，操作个数 𝑞q 满足 1 ≤𝑞 ≤2 ⋅1051≤q≤2⋅105．

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

参考代码（分块套树状数组 - 1s）

---|---

参考代码（树状数组套 Treap—TLE）

---|---

例题 2

Complicated Computations

给出一个序列 𝑎a，将 𝑎a 所有连续子序列的 MEX 构成的数组作为 𝑏b，问 𝑏b 的 MEX．一个序列的 MEX 是序列中最小的没出现过的 正整数 ．

序列的长度 𝑛n 满足 1 ≤𝑛 ≤1051≤n≤105．

观察 ：一个序列的 MEX 为 𝑚𝑒𝑥mex，当且仅当这个序列包含 11 至 𝑚𝑒𝑥 −1mex−1，但不包含 𝑚𝑒𝑥mex．

依次判断是否存在 MEX 为 11 至 𝑛 +1n+1 的连续子序列．如果没有 MEX 为 𝑖i 的连续子序列，那么答案即为 𝑖i．如果都存在，那么答案为 𝑛 +2n+2．

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

用一个数组 𝑌𝑗Yj 记录上一个值为 𝑎𝑗aj 的元素的位置，以 𝑗j 作为 𝑥x，𝑌𝑗Yj 作为 𝑦y，𝑎𝑗aj 作为 𝑧z．这样，计算段内是否包含 11 至 𝑖 −1i−1 就是一个三维偏序的问题．形式化的说，判断段 [𝑙,𝑟][l,r] 的 MEX 值是否为 𝑖i，就是看满足 𝑙 ≤𝑗 ≤𝑟,𝑌𝑗 ≤𝑙 −1,𝑎𝑗 ≤𝑖 −1l≤j≤r,Yj≤l−1,aj≤i−1 的点的个数是否为 𝑖 −1i−1．

如果在判断完值为 𝑖i 的元素之后再将对应的点插入，这时因为 [𝑙,𝑟][l,r] 内只存在 𝑎𝑗 ≤𝑖 −1aj≤i−1 的元素，所以上述三维偏序问题就可以转换为二维偏序的问题．

参考代码（分块套树状数组 - 78ms）

---|---

参考代码（线段树套 Treap-468ms）

---|---

本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：Tiphereth-A, Backl1ght, aaron20100919, Enter-tainer, Ir1d, ksyx, leoleoasd, Xeonacid, c-forrest 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用