笛卡尔树(Cartesian Tree)与区间最值查询(RMQ)

简单来说,笛卡尔树(Cartesian Tree)是一种特殊的二叉树,每棵子树的根节点都是整个子树的极值,并且对于这棵树进行中序遍历后的结果就是原序列(也就是所有点中序遍历正好对应了原数组的一段区间)。这样的树就是笛卡尔树。

定义与概念

笛卡尔树是一种特定的二叉树数据结构,可由数列构造,在范围最值查询、范围top k查询(range top k queries)等问题上有广泛应用。它具有堆的有序性,中序遍历可以输出原数列。笛卡尔树结构由Vuillmin(1980)在解决范围搜索的几何数据结构问题时提出。从数列中构造一棵笛卡尔树可以线性时间完成,需要采用基于栈的算法来找到在该数列中的所有最近小数。——维基百科

为了方便理解,先来看道例题吧:

例题:最大子矩形面积

题目描述

有一系列的长条状的矩形,宽度都为1,相邻的竖立在x轴上,求最大的子矩形。

题图

输入输出格式

输入格式

第一行输入一个整数 n (1\leqslant n \leqslant 100000)

第二行输入 n 个整数表示每个矩形的高度 h (1 \leqslant h \leqslant 10^9)

输出格式

输出最大子矩形的面积。

样例输入输出

样例输入

7
2 1 4 5 1 3 3

样例输出

8

解题思路

可以很容易看出,这题可以用单调栈做:可以对于每个点,可以构造出 left_iright_i 分别表示以当前的高度,向左、向右可以取到哪里。

这是单调栈的做法。其实另一种思路是 RMQ+递归:在 1~n 这段区间里找出最小值 A_i,然后以 i 为中心,把区间分成两半,左右分别和刚才一样找最小值、递归处理。这种方法就很想笛卡尔树了。

示例代码

给出这题用笛卡尔树实现的代码(建议先看下面再看代码)(有些地方写得很笨……没办法,我懒~)。

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=100005;
int n,a[maxn],ls[maxn],rs[maxn],fa[maxn],stk[maxn],top=0,sum[maxn];
long long ans;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline void DFS(int x){
    if (x<1||x>n) return;
    if ((long long)(sum[ls[x]]+sum[rs[x]]+1)*(long long)a[x]>ans) ans=(long long)(sum[ls[x]]+sum[rs[x]]+1)*(long long)a[x];
    sum[x]=sum[ls[x]]+sum[rs[x]]+1;
    DFS(fa[x]);
}
int main(){
    n=read();
    for (int i=1;i<=n;i++) a[i]=read();
    for (int i=1;i<=n;i++){
        if (a[i]>=a[stk[top]]||top==0){
            rs[stk[top]]=i;
            fa[i]=stk[top];
            stk[++top]=i;
        } else {
            while (a[stk[top]]>a[i]&&top>=1) top--;
            rs[stk[top]]=i;fa[i]=stk[top];
            ls[i]=stk[top+1];fa[stk[top+1]]=i;rs[i]=0;
            stk[++top]=i;
        }
    }
    for (int i=1;i<=n;i++) if (ls[i]==0&&rs[i]==0) DFS(i);
    printf("%lld\n",ans);
    return 0;
}

笛卡尔树的性质

要构造笛卡尔树,我们要先了解其性质。

  1. 结点一一对应于数列元素。即数列中的每个元素都对应于树中某个唯一结点,树结点也对应于数列中的某个唯一元素。

  2. 中序遍历(in-order traverse)笛卡尔树即可得到原数列。即任意树结点的左子树结点所对应的数列元素下标比该结点所对应元素的下标小,右子树结点所对应数列元素下标比该结点所对应元素下标大。

  3. 树结构存在堆序性质,即任意树结点所对应数值大/小于其左、右子树内任意结点对应数值。

举个例子,以下就是对于数列 \lbrace 2,1,4,5,1,3,3 \rbrace 构造的笛卡尔树(终于有一张原创的图了!不容易啊~):

笛卡尔树示例

先看第一条性质:结点一一对应于数列元素,很显然满足。再看第二条,对这棵树进行中序遍历

笛卡尔树与 RMQ

RMQ(区间最值问题)指的是给出一个序列,要求以 log_2n 的级别求出某个区间内的极值。一般的 RMQ 求法是:定义 F(i,j) 表示第 i 个元素往前推 2^j 个元素这段区间里的极值,这样便于修正(具体RMQ的做法这里不展开讲)。是不是感觉和上面的笛卡尔树有些联系?

一颗笛卡尔树里 i 元素到 j 元素的极值,就是他们的最近公共祖先的值。(请看上图仔细体会)

笛卡尔树的构造

知道了笛卡尔树的性质,我们就可以开始构造笛卡尔树了。对于上面那道题目,我们只需要维护一棵笛卡尔树,然后用单调栈存储从根节点到最后一个点的一段链(栈里除了第一个点以外每一个点都是上一个点的右儿子)。如果新加入一个元素 k,判断两种情况:

  1. 它比栈顶还大。因为是单调栈,可以直接加到栈顶。
  2. 它不比栈顶大。我们只需要在栈里找到它插入的位置,把比它大的一段链全都变成它的左子树,然后再把它插入。这样,在中序遍历的时候仍然是先遍历其左子树再遍历它自身,满足第二条性质;因为左子树都比它大,显然满足性质 1、3。

根据这种方法,很容易构造出笛卡尔树。详见代码。


参考

笛卡尔树 – 维基百科,自由的百科全书
(主要根据上课的PPT整理的~~)

本文采用 BY-NC-SA 4.0 协议,欢迎转载。如有错误欢迎指出。
本文链接: https://skywt.cn/posts/cartesian-tree/

发表评论

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

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。