专栏文章

笛卡尔树学习笔记

LLionBlaze
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minxhmej
此快照首次捕获于
2025/12/02 09:57
3 个月前
此快照最后确认于
2025/12/02 09:57
3 个月前
查看原文
因为只有模版题所以不好意思交全站推荐。
笛卡尔树就是 Treap，啊不说反了，Treap 是笛卡尔树。
笛卡尔树是一棵二叉树，每个节点包含两个属性：id\mathrm{id} 和 val\mathrm{val}。其中 id\mathrm{id} 两两不同。如果用 id\mathrm{id} 当做权值，则这棵树是一棵二叉搜索树。如果用 val\mathrm{val} 做权值，则它是一棵小根堆。由于不同的节点顺序建出来的笛卡尔树相同，我们通常把 id\mathrm{id} 当做下标。
下面随便写写三个用屁股都能想到的定理，可能没那么重要。
定理 11：任意一个满足 id\mathrm{id} 两两不同的节点序列都可以建出笛卡尔树。
证明：我们给出一个构造算法来证明这一点。
首先将序列按照 id\mathrm{id} 排序。然后找到 val\mathrm{val} 最小的节点（如果有多个找出任意一个），将其作为根节点，然后在其左边的所有元素中找出 val\mathrm{val} 最小的作为其左子结点，其右边所有元素中找出 val\mathrm{val} 最小的作为其右子节点，然后在左子树和右子树重复上述操作。显然其中序遍历的 id\mathrm{id} 值就是（排序后）原序列的 id\mathrm{id}，满足从小到大，所以是二叉搜索树。而每个父节点的 val\mathrm{val} 值都是其子树中（可能不唯一）最小的，所以满足小根堆性质。故这样建出来的树是二叉搜索树，证毕！□\square
定理 22：若 val\mathrm{val} 也两两不同，则能且仅能建出一棵笛卡尔树。
证明：存在性参见定理 11。
我们接下来证明定理 11 中给出的构造方式能够构造出所有的笛卡尔树（通过多个最小值选择不同值来构造不同的笛卡尔树）。
笛卡尔树的中序遍历一定是原序列（的排序后的结果）。所以，某个节点的左子树的中序遍历就是其子树的中序遍历中在这个节点左边的所有节点，右子树同理。
显然，算法的第一步可以选出所有可能的根节点。对于每个根节点，算法都能选出所有可能的左子结点和右子节点，以此类推。这样，算法能够构造出所有可能的笛卡尔树。
而当所有节点的 val\mathcal{val} 值两两不同时，算法没有选择的余地，每次的根节点都只能选出一个（因为不可能有相同的最小值），故笛卡尔树唯一，证毕！\sqrare\sqrare
不过需要注意的是，就算 val\mathrm{val} 有相同，笛卡尔树也可能唯一。考虑节点列表：
id\mathrm{id}val\mathrm{val}
1111
2222
3311
显然其笛卡尔树唯一。而笛卡尔树唯一的充要条件就是我们的构造算法每一步选出的最小值都唯一。
定理 33：若某个数字 xx 没有出现在 val\mathrm{val} 中，则把 val\mathrm{val} 中 xx 的前驱（可能有多个，选择任意一些都行）或者后继（同上，但是不能同时有前驱后继）改为 xx 最终还是原序列的合法的笛卡尔树。
证明：假设若干个权值为 vv 的节点权值被改为了 xx。显然 val\mathrm{val} 中没有权值在 vv 和 xx 之间的节点了。
假设修改后的序列的笛卡尔树为 TT，其中 TT 的若干个 xx 实际上是 vv。对于修改而来的节点，其父节点的权值为 vfv_f（不存在则为负无穷），左子结点为 vlv_l，右子节点为 vrv_r（不存在则为正无穷）。
如果 vf=xv_f=x，显然合法。否则 vfv_f 没有被修改过，且 vf≤xv_f\le x。分类讨论：如果 v<xv<x，则 vf≤vv_f\le v，将 xx 改回 vv 显然可以。否则 vf≥vv_f\ge v，将 xx 改回 vv 还是可以。左子结点和右子节点类似。证毕！□\square
这个定理实际上告诉我们，对于存在重复 val\mathrm{val} 的序列，我们如果只需要求出一个笛卡尔树，则可以对数列进行微调。比如包含了三个 11，且都是整数，则我们可以把这三个 11 修改为 1,1.1,1.21,1.1,1.2，得到的还是原序列的笛卡尔树。
这同时提供了定理 22 的一个不严谨的理解方式。
讲了这么多废话，接下来进入正题——如何构建一棵笛卡尔树？
我们可以使用定理 11 中的构造法，但是可能会被卡到平方级别（有序序列。是不是想到了快排？）。我们需要更好的构造方式。
我们发现，我们原本是按照前序遍历的方式构造的笛卡尔树，这样没有充分利用笛卡尔树的性质——实际上，既然笛卡尔树涉及到中序遍历，我们就应该采用中序遍历的方式。
对于当前得到的树，如果在序列中加入一个元素，这个节点应该被放在哪呢？看似只有两种可能——树的最右边的节点（即每次都走右儿子走到的节点，中序遍历的末尾）的右子节点，或者根节点的父亲，根节点作为其左子结点。实际上在这两者之间还有——顶替“右链”（即从根节点一直走右儿子，能够走到的所有点，包括根节点）上任何一个节点处，然后将这个节点的子树作为其左子树。因为它在右链上且它没有右儿子，所以它在中序遍历的结尾。原本的两种方法第一种是在右链的末尾插入，第二种是在右链的开头（根节点）处插入。
具体插在哪个节点处呢？我们发现它的 val\mathrm{val} 要不小于它的父节点，不大于它的左子结点。这样，就可以枚举处它所在的位置。
这样，我们只需要维护一个右链，就可以最终求出整棵树。
那么它的时间复杂度呢？还是平方级别的，每个节点都只有右子节点的树可以让它被迫每次遍历一遍右链。如何优化呢？很简单——反着在右链查找即可，也就是在右链的末尾向开头查找。这是因为，每个点如果被查找过程经过，那么它就会变为新插入的节点的左子树中的节点，不在右链中了。所以每个点至多被查找一次，所以均摊下来是 O(1)\mathcal O(1) 的，总时间复杂度是线性的。
代码。
CPP
// 我们不维护右链，甚至不存储右链的最后一个节点的指针，因为它就是最后一个节点。
#include <cstdio>

using namespace std;

class node
{
public:
    int val, l, r, fa;
} nodes[10000005];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &nodes[i].val);
        if (i == 1) nodes[i].l = nodes[i].r = nodes[i].fa = 0;
        else
        {
            nodes[i].r = 0;
            int v = i - 1;
            if (nodes[v].val < nodes[i].val)
            {
                nodes[v].r = i;
                nodes[i].fa = v;
            }
            else
            {
                do
                {
                    if (nodes[nodes[v].fa].val < nodes[i].val && nodes[i].val < nodes[v].val)
                    {
                        nodes[nodes[v].fa].r = i;
                        nodes[i].fa = nodes[v].fa;
                        nodes[v].fa = i;
                        nodes[i].l = v;
                        break;
                    }
                } while (v = nodes[v].fa);
            }
        }
    }
    long long x1 = 0, x2 = 0;
    for (int i = 1; i <= n; i++)
    {
        // printf("l[%d] = %d, r[%d] = %d\n", i, nodes[i].l, i, nodes[i].r);
        x1 ^= 1ll * i * (nodes[i].l + 1);
        x2 ^= 1ll * i * (nodes[i].r + 1);
    }
    printf("%lld %lld\n", x1, x2);
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...