笛卡尔树,是一种对于二元组 $(k,w)$ 进行构造的平衡树,其中 Treap 就是一种特殊的笛卡尔树。

在笛卡尔树中,每一个节点满足以下性质:

  • 权值 $k$ 满足二叉搜索树的性质。
  • 权值 $w$ 满足堆状结构的性质。

构造笛卡尔树的方法比较简单,以 $w$ 构成小根堆为例,过程如下:

  • 将 $k$ 作为关键字,从小到大插入节点 $u$,考虑维护一条从根节点一直想右子节点走的链。
  • 考虑从链的最深节点开始向上查找,找到第一个节点 $x$,满足 $x_w\leq u_w$。
  • 将 $x$ 的右子树改为 $u$,并将原先 $x$ 的右子树改为 $u$ 的左子树。

时间复杂度为 $\mathcal O(n)$。

top = root = 0;
for (int i = 1; i <= n; i++) {
  while (top > 0 && a[stk[top]] >= a[i]) top--;
  if (top == 0)
    root = i, son[root][0] = stk[1];
  else {
    son[i][0] = son[stk[top]][1];
    son[stk[top]][1] = i;
  }
  stk[++top] = i;
}

以上代码给出的是 $(i,a_i)$ 作为二元组的笛卡尔树构造,这种树也就是其 $k$ 为数组下标,这样的笛卡尔树有一个性质就是其子树内的节点的 $k$ 值连续,意味着代表原序列的一个区间。

笛卡尔树还可以在数据随机的情况下,高效地完成区间 RMQ 的问题,可以详见洛谷P3793 由乃救爷爷

最后修改:2020 年 08 月 22 日 11 : 01 PM
如果觉得我的文章对你有用,请随意赞赏