你不算线段树的吗
by Zechariah @ 2019-02-28 00:54:17
@[Zechariah](/space/show?uid=87283) 啊看错了，用的是ST表
by Zechariah @ 2019-02-28 00:54:51
写法不好，常数大呗
这里树剖+ST表，不开O2 385ms[评测记录](https://www.luogu.org/recordnew/show/16725637)
by Zechariah @ 2019-02-28 01:48:38
@[Zechariah](/space/show?uid=87283) 我跟您写法不太一样。。
我在树剖第二遍dfs中，记录每个点到其重链顶的max值，最后一段查询用线段树。这样每次还是log n的时间复杂度。如果数据特殊可以比st表快
by NaCly_Fish @ 2019-02-28 06:56:26
@[NaCly_Fish](/space/show?uid=115864) 虽然复杂度还是$log n$，但是你的常数会变大，况且线段树常数本来就比倍增大
by Cqdnse @ 2019-02-28 08:26:51
@[Cqdnse](/space/show?uid=63348) 我的意思是，如果询问比较少(与$n$不同阶)，我的方法会更快一点。。
毕竟st表的预处理还要n log n
总之就是看个人喜好了
by NaCly_Fish @ 2019-02-28 17:39:55
@[NaCly_Fish](/space/show?uid=115864) 只要复杂度没问题，还是尽量用简单的数据结构或算法，不容易出错
by Cqdnse @ 2019-02-28 19:19:13
常数什么的，没有正确性重要
by Cqdnse @ 2019-02-28 19:19:32