笛卡尔树

有一类数据结构叫笛卡尔树。

笛卡尔树构建在序列上。

假设我们有一颗笛卡尔树构建在序列a中,则树中每个节点维护两个值:(value, pos),满足a[pos]=value。每个节点有左右两个孩子。

  • 对于value满足 this->value <= this->lc->value && this->value <= this->rc->value
  • 对于pos满足 this->pos > this->lc->max_pos && this->pos < this->rc->min_pos

朴素的构建方法是\(O(N^2)\)的,如果我们像虚树那样维护最右链,从1…N扫描序列a来构建是\(O(N)\)的。
用最右链维护第一条性质,顺序扫描维护第二条性质。

有了这个笛卡尔树我们就可以解决奇怪的O(N)-O(1) RMQ问题了。

  1. 用笛卡尔树将序列转为树
  2. DFS这棵树
  3. 对DFS的序列做+1/-1RMQ

+1/-1 RMQ

(来自百度百科)

现在仍旧用A[0,N-1]表示问题中的数列,这里有|A[i]-A[i-1]|=1(i=1,2,…,N-1)成立。
将A分解为长度为l=[(log N)/2]的块。设Amin[i]为第i块中的最小值,B[i]为该最小值的位置。Amin[i]和B[i]的长度均为N/l, 所以用ST算法处理Amin数组的时空复杂度均为\(O(N/l* \log (N/l))=O(N/ \log N*( \log N- \log l))=O(N)\)。
预处理之后,对任意多连续的块进行的查询都能在O(1)时间内实现。余下的问题是如何进行块内查询。

注意到对任意一块中的块内查询的结果有影响的唯一因素是块内每相邻两个元素间的“升降关系”构成的序列。因为每两个元素之间的关系只有两种(“+1”、“-1”),而块的长度又只有l=[(log N)/2],所以本质不同的块最多有\(2^I=O(sqrt N)\)种。对每种块中所有可能的块内查询预处理出答案的时空复杂度是\(O(sqrt N*l^2)=O(N)\)(这里的O(N)表示不超过线性时间)。预处理出所有块的“类型”,并用二进制数存储的时间复杂度是O(N)。
此后,每次查询可以分为两种情况:
1、块内查询,答案已经被预处理出,只要在数组中找到它即可。
2、块间查询,可以分解为2个块内查询,和一个A’上的RMQ,三者的时间复杂度都是O(1)。
综上,我们给出了一个预处理时间为O(n),查询时间为O(1)的在线RMQ算法。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据