UOJ Logo huangsi的博客

博客

不算预处理,什么时候线段树比ST表还快?

2017-05-22 11:59:46 By huangsi

当你在上面跑费用流的时候。

评论

WrongAnswer
给个例题?
OldDriverTree
ST表查rmq比笛卡尔树和并查集都快哦~
BillXu2000
我们可以先把所有可行的输入枚举一遍,记下答案,然后直接查表,反正不算预处理(雾
Sengxian
我猜你在用数据结构优化建图。 可能 ST 表点数是 $O(n\log n)$ 的,而线段树边数是 $O(n\log n)$ 的,所以 ST 表不如线段树跑得快。

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。