请求加入题解区

Butterfly__qwq @ 2024-02-29 14:36:57

by 大眼仔Happy @ 2024-02-29 15:35:33

毕竟还是线段树板子

by fjy666 @ 2024-02-29 15:36:42

by fjy666 @ 2024-02-29 15:37:03

测符号打反了，是 >

by 大眼仔Happy @ 2024-02-29 15:38:08

@fjy666 你说得对，但是这位老哥认为自己的常数很优秀

by EnofTaiPeople @ 2024-02-29 15:55:53

支持 O(n^{1+eps})>O(n\log n) 的理论。

看上去常数巨大，事实上并没有正常常数的线段树/树状数组快。

理论上每次分三叉树是最优的，这类做法的复杂度不能声称为 O(\sqrt[k]n)，实际上是 O(k\sqrt[k]n)，在任何情况下都不能做到优于 O(\log n)，而且，不具有扩展性。

而且这根本就不是 Sqrt-Tree，Sqrt-Tree 的复杂度是 O(\log\log n) 的。

by 大眼仔Happy @ 2024-02-29 17:54:57

@EnofTaiPeople 好！

你从理论打败他，我从实践打败他

话说是为何 O(n^{1+eps})>O(n\log n)？

by Terry2022 @ 2024-02-29 18:02:41

其实这个做法可以做法可以做到 O(n^{\epsilon})-O(1) 或 O(1)-O(n^{\epsilon})，即使用类似树状数组区间加区间求和的差分技巧，但是实际上会带巨大的常数，取 O(n^{\frac{1}{3}}) 或 O(n^{\frac{1}{4}}) 就足够了，效率上上没有树状数组优，详见 一份实现。

这份代码实现了 O(n^{\frac{1}{3}})-O(1)，O(n^{\frac{1}{4}})-O(1)，O(1)-O(n^{\frac{1}{4}})，O(1)-O(n^{\frac{1}{3}})，由于实现时间较为古老，常数可能较大，更优的实现应该是按照 2^{k} 分块。

by Terry2022 @ 2024-02-29 18:09:51

跑的最快的似乎是 O(1)-O(n^{\frac{1}{3}})，当然也可能是评测机波动。

可供参考的提交记录：（由于比较古老，实现是不优的）

洛谷：

O(1)-O(\sqrt[4]{n})

O(1)-O(\sqrt[3]{n})

O(\sqrt[3]{n})-O(1)

O(\sqrt[4]{n})-O(1)

loj：

O(1)-O(\sqrt[4]{n})

O(1)-O(\sqrt[3]{n})

O(\sqrt[3]{n})-O(1)

O(\sqrt[4]{n})-O(1)

by Butterfly__qwq @ 2024-02-29 21:07:44

@大眼仔Happy 你说得对但是我根本没用快读，只用了ios::sync都只比你慢20ms

by Butterfly__qwq @ 2024-02-29 21:11:06

@EnofTaiPeople 但是这玩意常数虽大但是没线段树大吧，而且准确说应该是 O(k^2\sqrt[k]{n})吧