一种基于分块的数据结构

前言：这种数据结构于笔者在 4 个多月之前口胡出来，可能已有前人发现。若有，希望可以指出。

1 基本结构

考虑一个有序数组，支持如下操作：

这是一道块状链表的模板题，但是如果要求询问 O(1) 该如果做？

不妨设数组的最大长度为 n，考虑将其分块，每块块长为 k=\sqrt n。

对于每一块，使用一个长度为 k 的数组 a_i 维护其中的数，并再记录一个值 st，表示它对应到原数组的是 a_{i,st}-a_{i,k},a_{i,1}-a_{i,st-1}（就是循环记录）。

查询时，可以直接找到对应的数，O(1)。

插入时，找到对应的块，O(k) 将该块后面的数整体向后移一次。对于之后的块，需要把整块向后移一位,只需在 st-1 的位置赋值为原先前一个块的最后一个元素，并将 st 自减 1。总复杂度 O(k)+O(\dfrac{n}{k})=O(\sqrt n)。

删除类似。

和块状链表类似，这个数据结构也可以打懒标记。

插入/删除时，需要的操作是将一个没有标记的数加入一个有标记的块中，此时需要求逆运算。

若该运算不满足交换律，在区间修改时处理散块也需要求逆。

对于每个节点，都需要再维护一个时间，表示该节点什么时候加入本块中。

于是可以将问题转化为：查询之前某个时间到现在为止的标记总和。

由于满足结合律，可以使用线段树实现。

插入/删除：O(k)+O(\dfrac{n}{k}\log n)=O(\sqrt n\log n)。

区间修改：O(k\log n)+O(\dfrac{n}{k}\log n)=O(\sqrt n\log n)。

若满足交换律，则区间修改为 O(k)+O(\dfrac{n}{k}\log n)。可以取 k=\sqrt{n\log n}，则插入/删除、修改都是 O(\sqrt{n\log n})。

特别的：若操作为区间赋值，则可以不用线段树维护，每个块维护最晚一次懒标记的时间与标记本身。插入/删除、修改都是 O(\sqrt n)。

每个块维护整块信息，区间询问 O(\sqrt n)，和块状链表相比毫无优势。

和块状链表相比，O(1) 单点查询非常有优势（可能可以用于奇怪的根号平衡？），也可以以较优的复杂度维护大部分区间操作，区间查询不优于块状链表。