笛卡尔树

发表于 | 分类于 |

前置知识:二叉搜索树+堆+单调栈

笛卡尔树的节点包含两个基本属性(k,w),在树中的k值满足了二叉搜索树的性质(左子节点的k值<=根节点的k值<=右子节点的k值)，而w值满足了堆的性质(根节点的w值>任意子节点的w值)

若我们采用数组中的下标作为k值，数组中的元素值作为w值，易知，选定一个根节点，则其子树+其本身为一个区间，而根节点的w值即为区间最值

如何构造，按k值顺序，往树中插入节点，节点位置取决于w，因为k值从小到大，故我们总是往右插入节点，用一个单调栈来维护右链

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int ls[200005],rs[200005];//存左儿子、右儿子
int stk[200005];//维护右链单调栈
int w[200005];//w数组
int n;//节点个数
void build()//大顶堆的笛卡尔树构造
{
    int top=0;//表示栈顶
    for(int i=1;i<=n;i++)
    {
        int k=top;
        while(k&&w[i]<=stk[k])
        {
            k--;//弹出栈直至栈空或找到比w[i]大的元素
        }
        if(k)rs[stk[k]]=i;//若栈不空，则变更栈顶元素的右儿子
        if(k<top)ls[i]=stk[k+1];//将本来栈顶元素的右儿子变为左儿子
        stk[++k]=i;//将当前节点压入栈
        top=k;//更新top
	}
}

应用:统计满足条件的区间个数(如区间最大值*2<=区间sum),区间最值与区间长度的相关计算(如统计图中的最大矩形面积)