笛卡尔树简介 ← 基于单调栈创建

____simple_html_dom__voku__html_wrapper____>

【笛卡尔树简介】
● 笛卡尔树（Cartesian Tree）是由一个序列 a[1], a[2], …, a[n] 唯一确定的二叉树，其同时满足二叉查找树（BST）性质和堆性质。笛卡尔树的每个结点包含一对儿信息 (pri, val)，其中 pri 固定为元素在原序列中的下标 i，决定了结点在笛卡尔树中的位置。val 为序列元素的值 a[i]，决定了笛卡尔树中结点间的堆序关系。

● 笛卡尔树结构唯一、固定、不可改变
笛卡尔树不是动态平衡树，不支持随意插入或删除操作，只能通过序列重建。只要序列保持不变，对应的笛卡尔树结构就唯一、固定、不可改变。换句话说，笛卡尔树由一个序列唯一确定，不同序列对应不同的笛卡尔树。

● 笛卡尔树（Cartesian Tree）于 1980 年由 Jean Vuillemin 正式提出，其名称源自笛卡尔坐标系。原因在于，笛卡尔树将序列 a[1], a[2], …, a[n] 中的每个元素 a[i] 映射为笛卡尔坐标系中的点（横坐标 pri = 下标 i, 纵坐标 val = 序列值 a[i]）。

From：https://oi-wiki.org/ds/cartesian-tree/

● 笛卡尔树示意图，无法直观体现 val 的具体大小。这是因为，val 是用来 “建造” 笛卡尔树的规则，不是用来 “画在” 笛卡尔树示意图里的数值。

● 笛卡尔树结点纵坐标 val 的差异，不能通过在示意图中把结点 “画得高一点、低一点” 来体现，只靠【谁能当谁的爸爸】来体现。

● 笛卡尔树示意图中，结点的垂直高度（层数）表示结点在树中的深度，仅用于可视化排版。同一层的结点不代表 val 相等，只表示它们在树结构中的层级相同。

​​​​​​​●​​​​​​​ 笛卡尔树满足两条性质：
（1）按 pri 构成二叉搜索树结构，等价于中序遍历结果与原序列完全一致；
（2）按 val 满足堆序关系（小根堆或大根堆）。
简言之，一棵笛卡尔树，pri 决定结点的左右位置，val 决定结点的堆序层级。即，pri 管左右关系（中序）、val 管父子关系（堆），两个维度互不干扰，永远不会冲突、不会掣肘。

● ​​​​​​​笛卡尔树（Cartesian Tree）的核心作用是把序列的区间最值问题转化为树上的 LCA（最近公共祖先）问题，从而实现 O(n) 预处理、O(1) 查询的高效解法。这得益于笛卡尔树的关键性质，即：序列区间 [L, R] 的最小值 = 笛卡尔树上结点 L 与 R 的 LCA。换句话说，笛卡尔树 = 序列的 “区间最值树形化”。笛卡尔树是算法竞赛与数据结构优化的核心工具。

●​​​​​​​ 笛卡尔树 O(n) 构建法（小根堆版）
笛卡尔树构建步骤：以序列首元素为根，遍历剩余元素逐个插入。
（1）新元素 val 更小：取代原根，将原根设为新元素的左子树。
（2）新元素 val 更大：沿根的最右路径向下查找。
找到第一个 val 比新元素大的结点 → 替换该结点，将其设为新元素的左子树。
未找到（所有最右路径结点 val 都更小）→ 直接作为最右路径最后一个结点的右子树。
（3）重复上述步骤，直至所有元素遍历完成。

● 笛卡尔树的根只由 val 决定，跟 pri 完全无关！选好根之后，直接将序列元素按下标切成两半：下标<根下标 → 全部进左子树、下标>根下标 → 全部进右子树。然后，左右子树再递归。即：左子树里再找 val 最小当左孩子、右子树里再找 val 最小当右孩子。

​​​​​​​● 笛卡尔树构建完成后必须满足两大条件：
（1）中序遍历结果与原序列完全一致
（2）整棵树满足堆序关系

● 无论序列里有没有重复值、是否有序、是否乱序。任意一个序列，都可以唯一构造出一棵笛卡尔树。

​​​​​​​●​​​​​​​ 基于序列 [5, 6, 3, 8, 9, 1, 4, 7, 2] 构建笛卡尔树的过程，如下所示。

●​​​​​​​ 笛卡尔树与单调栈
笛卡尔树在构建过程中，常借助“单调栈”，以保证在线性时间内完成笛卡尔树的构建。单调栈中保存的始终是笛卡尔树的右链，即由笛卡尔树的“根结点、根结点的右儿子、根结点的右儿子的右儿子、……”组成的链。

【笛卡尔树算法实例】
●​​​​​​​ 洛谷 P5854：https://blog.csdn.net/hnjzsyjyj/article/details/138353654

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e7+5;
int a[maxn];
int n;
LL lson[maxn],rson[maxn];
LL ans1,ans2;
stack<int> s;
int read() { //fast read
    int x=0,f=1;
    char c=getchar();
    while(c<'0' || c>'9') { //!isdigit(c)
        if(c=='-') f=-1; //- is a minus sign
        c=getchar();
    }
    while(c>='0' && c<='9') { //isdigit(c)
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; i++) {
        a[i]=read();
        while(!s.empty() && a[s.top()]>a[i]) {
            lson[i]=s.top();
            s.pop();
        }
        if(!s.empty()) rson[s.top()]=i;
        s.push(i);
    }
    for(int i=1; i<=n; i++) {
        ans1=ans1^(i*(lson[i]+1));
        ans2=ans2^(i*(rson[i]+1));
    }
    printf("%lld %lld",ans1,ans2);
    return 0;
}
/*
in:
5
4 1 3 2 5
out:
19 21
*/

● AcWing 4279：https://blog.csdn.net/hnjzsyjyj/article/details/158356691

#include <bits/stdc++.h>
using namespace std;
const int maxn=35;
int a[maxn];
int lson[maxn],rson[maxn];
int fa[maxn];
int n;
stack<int> s;
void bfs(int root) {
    queue<int> q;
    q.push(root);
    while(!q.empty()) {
        int t=q.front();
        q.pop();
        cout<<a[t]<<" ";
        if(lson[t]!=0) q.push(lson[t]);
        if(rson[t]!=0) q.push(rson[t]);
    }
}
int main() {
    cin>>n;
    for(int i=1; i<=n; i++) {
        lson[i]=rson[i]=fa[i]=0;
    }
    for(int i=1; i<=n; i++) { //Cartesian Tree
        cin>>a[i];
        while(!s.empty() && a[s.top()]>a[i]) {
            lson[i]=s.top();
            fa[s.top()]=i;
            s.pop();
        }
        if(!s.empty()) {
            rson[s.top()]=i;
            fa[i]=s.top();
        }
        s.push(i);
    }
    //Find root
    int root=0;
    for(int i=1; i<=n; i++) {
        if(fa[i]==0) {
            root=i;
            break;
        }
    }
    bfs(root);
    return 0;
}
/*
in:
10
8 15 3 4 1 5 12 10 18 6
out:
1 3 5 8 4 6 15 10 12 18
*/