专栏文章

笛卡尔树

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

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@min0r4cj
此快照首次捕获于
2025/12/01 18:41
3 个月前
此快照最后确认于
2025/12/01 18:41
3 个月前
查看原文

笛卡尔树

笛卡尔树是一种二叉树，每个节点有键值 (k,w)(k,w)。要求 kk 满足二叉搜索树的性质，ww 满足堆的性质。
  • 二叉搜索树：xx 左子树所有 kk 比 kxk_x 小，xx 右子树所有 kk 比 kxk_x 大。
  • 小根堆堆：wxw_x 比 wlson,wrsonw_{lson},w_{rson} 小。
常使用下标作为 kk，值作为 ww。构建出来的树即每次按照区间最大值分治得到的树。
存在 O(n)O(n) 建树方法。
下标从小到大遍历，根据二叉搜索树的性质，当前点应该加在最右边。称从当前根节点一直向右儿子遍历得到的路径为“右链”，我们先把当前点放在右链尾部。
接下来进行调整使其满足小根堆的性质，若 wx<wfaw_x<w_{fa}，将 fafa 和其左子树一起变成 xx 的左子树，xx 变为父亲。
使用栈维护“右链”，每个点只会进出一次，故为 O(n)O(n)。
C
void build(){
	for(rg i=1;i<=n;i++){
		while(top>0&&a[st[top]]>a[i])ls[i]=st[top--];
		if(st[top]!=0)rs[st[top]]=i;
		st[++top]=i;
	}
}

评论

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

正在加载评论...