数据结构: 笛卡尔树

笛卡尔树

• 笛卡尔树中的笛卡尔指的是二元组，笛卡尔树针对第一元素是一棵二叉搜索树、针对第二元素是一个最大/最小堆；由二叉搜索树的性质，当第一、第二元素都不重复时，笛卡尔树是唯一的 根据定义，笛卡尔树其实就是一个树堆的特例；平常使用中，通常第一元素是数组下标、而第二元素是数组值，对应到树堆就是数组下标是键，数组值是优先级 也就是说，数据中给出的数组值需要是比较随机的，否则笛卡尔树就退化成链表了

• 笛卡尔树的用处：比较小众，适用于维护连续区间值的问题，例如：

  • 需要快速知道每一个元素a_i扩展出去的连续区间[l,r]，区间满足i ∈ [l,r]且a_j ≤ a_i, j ∈ [l,r] 这样的需求可以用两次单调栈得到每个元素的l、r，也可以建一个最大堆笛卡尔树来维护
  • 需要维护区间最值，当然可以用线段树维护，但也可以用笛卡尔树(转化为LCA问题，[l,r]的最值就是a_lca(l,r))

• 树的构造：和树堆类似，以最小堆笛卡尔树举例，维护一个栈顶元素始终最大的单调栈，从栈底到栈顶表示一条由根结点到最右结点的链，即栈顶元素表示当前树的最右结点 由于第一元素通常是数组下标，所以从左到右插入元素即可 每插入一个元素a_i，需要在单调栈中找到第一个比a_i小的结点，然后使a_i成为该结点的右儿子，如果它本身就有右儿子，则让整棵右子树成为a_i的左子树即可 此外，如果栈为空，则当前结点将成为根结点 由于每个元素最多进出栈一次，所以建树是O(n)的 实际上对应于树堆的建树过程，这就相当于先对数组值排序再O(n)建树，而笛卡尔树中，数组下标恰好是自然有序的

• // p为原数组, 范围[1, n]; tr[][2]为树, rt为根结点编号
  stack<int> stk;
  rt = 1;
  stk.push(1);    // 插入首元素
  for (int i = 2; i <= n; ++i) {
      while (!stk.empty() && p[stk.top()] > p[i]) {
          stk.pop();
      }
      if (stk.empty()) {  // 说明该结点是根结点
          tr[i][0] = rt;  // 原来的根结点作为左儿子
          rt = i;
      }
      else {
          tr[i][0] = tr[stk.top()][1];    // 使原本的右儿子成为当前结点的左儿子
          tr[stk.top()][1] = i;           // 使当前结点成为栈顶结点的右儿子
      }
      stk.push(i);    // 当前结点成为栈顶
  }

例题

• [TJOI2011] 树的序 本题题意言简意赅，就是要你根据它给的顺序建BST，然后输出其前序遍历；然而一般的BST建树时极其容易退化为O(n²)，所以考虑用构造笛卡尔树的方式建树 考虑建成之后，结点的键值k是构成BST的，且所有父亲结点的插入时间都比其儿子结点的插入时间早，构成最小堆；因此考虑二元组 < k, t>建笛卡尔树，因为k ∈ [1,n]且不重复，故将其看作数组下标即可