关于线段树

学术版

Register_int @ 2022-07-14 11:54:56

在我之前已经有人提到了三叉线段树的优化。我的想法是这样的：讲线段树的每一个节点按层交替设为二叉或三叉。这样的话也能更好的逼近 e 叉树的效率。如果该优化可以实现的话，那就有一种可能：利用 e 的无穷级数形式，分别计算线段树每个节点的叉数，使得其在渐进意义上逼近 e 叉树。本蒟蒻太菜了，想不出构造性的实现，特此求助各位巨佬。

by irris @ 2022-07-14 11:59:24

我记得 Sol1 讲过二叉和四叉相结合的，但是我找不到了（

by fjy666 @ 2022-07-14 12:10:15

但是这么搞的话合并信息常数就大了，所以总时间复杂度常数不变吧

by critnos @ 2022-07-14 12:19:32

有趣

by FunnyCreatress @ 2022-07-14 12:26:53

我的意见是，这种东西不太能等价于简单的取平均。