UOJ Logo f321dd的博客

博客

关于无修改区间问题

2018-08-14 21:35:38 By f321dd

对于可以O(1)合并的具有结合律的信息,可以使用vEB树,每个节点处理前缀和后缀信息。对于在一棵树上查询的区间,要么完全被某个子树完全包含,要么可以拆成一个子树的后缀、一个所有子树的vEB树上的可空的区间,以及另一个子树的前缀。空间复杂度O(nloglogn),预处理时间复杂度O(nloglogn),查询复杂度O(loglogn)。不过没啥用,应该跑不过高效实现的复杂度较高的方法。

好像挺显然的,不知道有没有人讲过。

UPD:经过讨论发现可以按logn大小进行k层分块。设$\log^{(m)}$表示连续取m次log,若每层都采用O(nlogn)-(1)维护块,则可以做到$O(n)$-$O(\log^{(k)}n)$,且对于随机询问期望O(1)。k=1时应该相当有实用价值。

多层线段树应该是类似的。

评论

orzzzzzz
直接上多层的线段树可以做到log*n吧,不过没啥用就是了
fjzzq2002
按logn大小进行1层分块应该lxl已经普及了( 可以当常数很小的O(n)-O(1) rmq用

发表评论

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