社区讨论

一种类分块代替文艺平衡树的数据结构

学术版参与者 7已保存回复 10

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
10 条
当前快照
1 份
快照标识符
@mkjd5ex7
此快照首次捕获于
2026/01/18 14:36
上个月
此快照最后确认于
2026/01/21 21:10
4 周前
查看原帖
本人觉得文艺平衡树太难写了,于是突发奇想发明了一种可能是假的数据结构。
准备工作:一个存储块端点次序的链表next和逆链表pre,每个块的大小数组siz,块内元素数组b,翻转标记数组tag。由于本分块每块大小不一样,故存储siz是必要的。把数组按块长p正常分块,处理出上述的数组。
区间反转:首先遍历链表,找出端点l,r所在的块。当l,r在同一块时,下传翻转标记tag,再暴力翻转区间。当l,r在不同块时,暴力交换散块内元素(注意这就是每块大小不一样的原因),再在链表上暴力交换两边的整块,所有整块翻转标记取反。
注意到这种数据结构很容易被卡,本人设计了两种维护平衡的操作——合并和分裂。
合并:遍历块时检测到块长小于q,下传翻转标记tag,看左右相邻的块,哪个小就往哪个合并。
分裂:遍历块时检测到块长大于r,下传翻转标记tag,把原块分裂成siz/p个小块。
此时维护块端点次序的数据结构就要支持高效插入删除,这就是用链表的原因。
我把这个东西扔给deepseek,他说这个数据结构在p=sqrt(n),q=p/2,r=2p时均摊复杂度是单次翻转sqrt(n),我感觉比较奇怪。
我也想成为发明全面替代oi史上第一难调毒瘤数据结构文艺平衡树的oi大英雄。不知道这种数据结构还会不会被卡,有没有大佬会用势能分析算一下均摊复杂度,设计一下p,q,r的值,或者构造一个hack让我的梦想破灭。
回复必关!

回复

10 条回复,欢迎继续交流。

正在加载回复...