手机版 欢迎访问it开发者社区(www.mfbz.cn)网站

当前位置: > 开发

【学习笔记】笛卡尔树

时间:2021/10/28 14:52:58|来源:|点击: 次

一种用于解决和区间最值相关的满足 堆性质 的二叉树。

由于笛卡尔树建立在 区间上 ,所以也具有二叉搜索树的性质。

用途

对于一些有区间限制的模型的转换。

构建

考虑从左往右扫描数组,用一个栈来维护树的右链,然后将新增的节点 u 找到右链中合适的位置插进去,再将 u 入栈。

时间复杂度 o(n) 。

void build() {
	for(int i=1;i<=n;i++) {
		while(cnt&&p[s[cnt]]>p[i]) {
			rson[s[cnt]]=lson[i];
			lson[i]=s[cnt];
			cnt--;
		}
		if(cnt) {
			rson[s[cnt]]=i;
		}
		s[++cnt]=i;
	}
}

Copyright © 2002-2019 某某自媒体运营 版权所有