题目分析

本题要求实现一个数据结构，支持两种操作：

单点插入：在指定位置前插入一个元素

单点查询：查询指定位置的元素值

与之前的问题不同，本题涉及动态插入操作，会改变序列的长度和结构。

算法设计

对于动态插入问题，传统的固定分块方法会遇到困难：

插入操作会改变块的大小

频繁插入可能导致某些块过大，影响效率

需要动态维护块的结构

分块+链表混合方法

我们采用分块与链表相结合的方法：

数据结构设计：

每个块使用 vector 或 list 存储元素

维护块的大小信息

设定块大小的阈值

核心操作：

插入操作：

找到插入位置所在的块

在块内相应位置插入元素

如果块过大，进行分裂操作

查询操作：

找到查询位置所在的块

返回块内相应位置的元素

块的重构：

当块大小超过阈值时，将块分裂为两个块

定期进行全局重构，保持块大小平衡

算法复杂度分析

时间复杂度

插入操作：

平均情况：$O(\sqrt{n})$（找到对应块 + 块内插入）

最坏情况：$O(n)$（需要重构时）

查询操作：$O(\sqrt{n})$

重构操作：$O(n)$，但发生频率较低

空间复杂度

$O(n)$：存储所有数据

关键优化点

动态块大小管理：

设定块大小阈值

块过大时进行分裂

定期全局重构保持平衡

数据随机性的利用：

题目说明数据随机生成

在随机数据下，插入操作相对均匀

块的大小分布相对平衡

重构策略：

局部重构（块分裂）：处理单个块过大的情况

全局重构：恢复理想的块大小分布

代码总结

本题展示了如何将分块算法应用于动态序列问题。通过结合分块与动态数据结构的思想，我们实现了高效的插入和查询操作。关键点在于：

利用分块降低单次操作复杂度

通过块分裂和重构维持性能

根据数据特性（随机生成）优化算法设计

这种方法在数据随机的情况下表现良好，适用于中等规模的数据处理需求。