众所周知,线段树、平衡树这一类树形数据结构,面对比较大的数据,时间复杂度常数会较大。然而,面对小数据,某些版本(比如我)的线段树时间复杂度的常数也大得明显。
在做 P1253 时,我便发现了这个问题。在本题中,有一组数据明显是放水的——n=q=1,这个测试点,即使是暴力,也大概率可以在 3ms 内搞定。而我的线段树,却花了 6ms 才完成(开 O2 甚至更慢)。确实,线段树在回答询问前需要先进行较多的预处理,但是 n=1 时,这种预处理的量是极少的,而回答所需的时间也很少。然而,提交记录中,却也有一些是花了 5ms 以上才完成该组数据的。不过,我的线段树的总效率却还不错(如最后一个点可以在 1.2s 内完成)。除了该题,P3373 等也是如此。
大家知道这种“常数”是由什么引起的吗?有什么方法,能帮我们摆脱这些“常数”的困扰?