块状数组

数据结构 / block-array

本地源文件：docs/ds__block-array.md

块状数组

建立块状数组

块状数组，即把一个数组分为几个块，块内信息整体保存，若查询时遇到两边不完整的块直接暴力查询．一般情况下，块的长度为 𝑂(√𝑛)O(n)．详细分析可以阅读 2017 年国家集训队论文中徐明宽的《非常规大小分块算法初探》．

下面直接给出一种建立块状数组的代码．

实现

---|---

其中 `st[i]` 和 `ed[i]` 为块的起点和终点，`size[i]` 为块的大小．

## 保存与修改块内信息

### 例题 1：[教主的魔法](https://www.luogu.com.cn/problem/P2801)

两种操作：

  1. 区间 [𝑥,𝑦][x,y]![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 每个数都加上 𝑧z![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)；
  2. 查询区间 [𝑥,𝑦][x,y]![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 内大于等于 𝑧z![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 的数的个数．

我们要询问一个块内大于等于一个数的数的个数，所以需要一个 `t` 数组对块内排序，`a` 为原来的（未被排序的）数组．对于整块的修改，使用类似于标记永久化的方式，用 `delta` 数组记录现在块内整体加上的值．设 𝑞q![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 为查询和修改的操作次数总和，则时间复杂度 𝑂(𝑞√𝑛log⁡𝑛)O(qnlog⁡n)![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)．

用 `delta` 数组记录每个块的整体赋值情况．

实现

---|---

例题 2：寒夜方舟

两种操作：

  1. 区间 [𝑥,𝑦][x,y] 每个数都变成 𝑧z；
  2. 查询区间 [𝑥,𝑦][x,y] 内小于等于 𝑧z 的数的个数．

用 delta 数组记录现在块内被整体赋值为何值．当该块未被整体赋值时，用一个特殊值（如 0x3f3f3f3f3f3f3f3fll）加以表示．对于边角块，查询前要 pushdown，把块内存的信息下放到每一个数上．赋值之后记得重新 sort 一遍．其他方面同上题．

实现

---|---

## 练习

  1. [单点修改，区间查询](https://loj.ac/problem/130)
  2. [区间修改，区间查询](https://loj.ac/problem/132)
  3. [【模板】线段树 2](https://www.luogu.com.cn/problem/P3373)
  4. [「Ynoi2019 模拟赛」Yuno loves sqrt technology III](https://www.luogu.com.cn/problem/P5048)
  5. [「Violet」蒲公英](https://www.luogu.com.cn/problem/P4168)
  6. [作诗](https://www.luogu.com.cn/problem/P4135)

* * *

>  __本页面最近更新： 2026/1/7 08:56:54，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/ds/block-array.md)
>  __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/ds/block-array.md "edit.link.title")
>  __本页面贡献者：[Ir1d](https://github.com/Ir1d), [R-G-Mocoratioen](https://github.com/R-G-Mocoratioen), [Enter-tainer](https://github.com/Enter-tainer), [Henry-ZHR](https://github.com/Henry-ZHR), [ksyx](https://github.com/ksyx), [ouuan](https://github.com/ouuan), [Alpacabla](https://github.com/Alpacabla), [chenyanlann](https://github.com/chenyanlann), [iamtwz](https://github.com/iamtwz), [Marcythm](https://github.com/Marcythm), [partychicken](https://github.com/partychicken), [StudyingFather](https://github.com/StudyingFather), [Tiphereth-A](https://github.com/Tiphereth-A), [zhuzeyu22](https://github.com/zhuzeyu22)
>  __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用