是否存在支持O(log n)时间复杂度的随机插入、删除与区间求和的数据结构？

线段树依赖固定的底层数组结构，确实没法优雅处理动态随机插入和删除——每次操作都要重构或调整结构，时间复杂度容易退化。针对你需要的三个操作，推荐两种更适配的数据结构：

1. 维护子树信息的平衡二叉搜索树（Treap/Splay/AVL） #

给每个节点额外维护两个字段：

• size：当前子树的元素总数
• sum：当前子树的元素总和

所有操作都能做到O(log n)时间复杂度：

• Insert(k, x)：通过size定位第k个位置的插入点，完成插入后，回溯更新路径上所有节点的size和sum
• Delete(k)：同样用size找到第k个元素，删除后更新路径上的size和sum
• Summation(l, r)：转化为「前r个元素的和」减去「前l-1个元素的和」，而前k个元素的和可以通过遍历树时累加符合条件的子树sum快速计算

2. 分块链表（块状数组） #

把数据拆分成若干固定大小的块，每个块维护：

• 块内元素计数
• 块内元素总和

操作逻辑：

• Insert(k, x)：找到k所在的块，若块大小超过预设阈值则分裂，直接在块内插入元素，更新块的计数和总和
• Delete(k)：定位到k所在块，删除元素后若块过小可与相邻块合并，同步更新计数和总和
• Summation(l, r)：遍历覆盖[l,r]的所有块，累加完整块的总和，再加上两端不完整块内的目标元素和

这种方法时间复杂度是O(√n)，实现难度远低于平衡树，适合对代码复杂度要求不高的场景

如果硬要基于线段树思路，也可以考虑动态开点线段树配合虚拟坐标，但本质是把元素位置映射到一个超大虚拟区间，插入相当于赋值、删除相当于置0，这种方式会浪费空间，且维护虚拟区间的逻辑繁琐，完全不如上面两种方案优雅。

内容的提问来源于stack exchange，提问作者Revive W