范围查询问题

Published: by Creative Commons Licence

  • Tags:

多维区间查询问题

一维查询问题一般都很简单,可以直接上线段树,不仅支持查询还能很好地支持修改,每次操作时间复杂度为$O(\log_2n)$。

一般二维查询问题可以离线请求后用线段树来$O(n\log_2n)$时间复杂度和$O(n)$空间复杂度解决,如果强制在线可以用持久化线段树$O(n\log_2n)$时间空间复杂度解决。如果还要求支持修改,那么离线的话,可以转换成三维问题(修改发生的时间作为第三个维度的值),如果要求必须在线,则需要上树套树这种复杂的数据结构才行,时间复杂度为$O(n(\log_2n)^2)$,但是如果数据量不大的话,可以试用一下四方树,时间复杂度为$O(n\sqrt{n})$,虽然看上去复杂度还不如树套树,但是常数小还好写。

而如果问题上升到三维,对于离线问题,常数较小的方法就是使用CDQ分治,时间复杂度为$O(n(\log_2n)^2)$,其余方法都不太好(在时间复杂度这么大的情况下,常数就非常重要了,CDQ分治使用的是BIT而非线段树,因此常数特别的小)。如果强制在线可以考虑使用KD-Tree,每次查询的时间复杂度$O(n^{2/3})$。

如果维度更高,只推荐KD-Tree了,其它的方式太复杂了。

题目1:给定$n$个字符串$s_1,\ldots,s_n$,给定$q$个请求,第$q$个请求给定前缀后缀和长度范围,要求找出有多少字符串满足所有的特性。其中$1\leq n,m\leq 3\times 10^5$,且输入的字符串总长度不超过$10^6$,字符串仅包含小写字母。

这里需要注意到,如果我们把字符串丢到前缀树中维护,并计算dfs序,那么前缀和后缀实际上分别圈定了一个范围。现在我们可以认为每个字符串可以由三维向量$(a,b,c)$,其中$a$为字符串的dfs序,$b$为字符串反转后的dfs序,$c$为字符串长度。而每个请求实际上对应一个三维区间查询。

考虑到题目可以离线,结合上面提到的策略,这里的最优实现方案是使用CDQ分治。时间复杂度为$O(n(\log_2n)^2)$。

提供一道题目