[学习笔记]笛卡尔树

不知不觉，这估计是自从我用这个博客以来“停更”最长的了。各种奇奇怪怪的原因综合在一起导致连续三个月没有写任何博客。其实过去半年感觉投入到ACM的时间就有点少。最近几天也是。话说笛卡尔树我从前一直没听说过（汗），最近比赛完后看题解才知道这玩意儿。。。

介绍

笛卡尔树是一种特定二叉树数据结构，可由数列构造，在范围最值查、范围top k查询（range top k queries）等问题上有广泛应用。它具有堆的有序性，中序遍历可以输出原数列。笛卡尔树结构由Vuillmin(1980)在解决范围搜索的几何数据结构问题时提出。从数列中构造一棵笛卡尔树可以线性时间完成，需要采用基于栈的算法来找到在该数列中的所有最近小数。

于维基百科上的图例能很好地展现它的性质：

实现细节

构造

我们固然可以通过一个个插入来构造笛卡尔树，虽然平均时间复杂度为\(O(n \log n)\)，但是在成链的条件下会退化为\(O(n^2)\)。而若我们使用单调栈，则可以直接实现\(O(n)\)的时间复杂度。

使用单调栈构造的主要思路是：维护一个存储了从根节点一直走右儿子到当前插入节点的所有节点的栈。比如当我们插入完了上图中的\(10\)时，单调栈存储的便为\([1, 8, 10]\)（此时\(8\)还是\(1\)的右儿子）。我们令栈顶的值为now，然后我们尝试取插入下一个数next。此时有如下三种情况：

\(next > now\): 此时我们直接令next为now的右儿子，并且令now原来的右儿子为next的左儿子；
\(next < now\): 将栈顶取出，然后再令当前栈的栈顶为now；
栈为空：令当前根节点的父亲指向next，并将next设为根节点。

代码实现如下：

stack<Node*> s;
struct CartesianTree
{
    Node *root;

    CartesianTree(int *a, int n)
    {
        s = stack<Node *>();

        for (int i = 0; i<n; i++)
        {
            Node *next = new Node(a[i]);
            Node *last = NULL;
            while (!s.empty())
            {
                if (s.top()->val < next->val)
                {
                    Node *tmp = s.top();

                    if (tmp->son[R])
                        tmp->son[R]->fa = next;
                    next->son[L] = tmp->son[R];

                    tmp->son[R] = next;
                    next->fa = tmp;

                    break;
                }

                last = s.top();
                s.pop();
            }

            if (s.empty() && last)
            {
                next->son[L] = last;
                last->fa = next;
            }

            s.push(next);
        }

        while (!s.empty())
        {
            root = s.top();
            s.pop();
        }
    }
};

例题

hdu 1506

题目来源：hdu

分析

题目给定了长度为\(10^5\)的h[]。要求求出最大的矩形。

我们可以构造一个笛卡尔树。由于笛卡尔树的性质可得，一个节点的子节点一定都大于该节点并且与它相邻。所以对于每个节点，高度为该子节点高度的最大矩形的面积便为\(size \times height\)。取所有节点的\(max\)即可。

代码

#include <iostream>
#include <algorithm>
#include <stack>

#define L 0
#define R 1
#define MAXN 100100

using namespace std;

struct Node
{
    int height;
    int size;
    Node *fa;
    Node *son[2];

    Node(int height = 0)
    {
        this->height = height;
        size = 1;
        fa = NULL;
        son[0] = son[1] = NULL;
    }
};
int cnt;

stack<Node*> s;
struct CartesianTree
{
    Node *root;

    CartesianTree(int *a, int n)
    {
        s = stack<Node *>();

        for (int i = 0; i<n; i++)
        {
            Node *next = new Node(a[i]);
            Node *last = NULL;
            while (!s.empty())
            {
                if (s.top()->height < next->height)
                {
                    Node *tmp = s.top();

                    if (tmp->son[R])
                        tmp->son[R]->fa = next;
                    next->son[L] = tmp->son[R];

                    tmp->son[R] = next;
                    next->fa = tmp;

                    break;
                }

                last = s.top();
                s.pop();
            }

            if (s.empty() && last)
            {
                next->son[L] = last;
                last->fa = next;
            }

            s.push(next);
        }

        while (!s.empty())
        {
            root = s.top();
            s.pop();
        }
    }

    long long run(Node *node = NULL)
    {  
        if (node==NULL)
            node = root;

        long long ans = 0;

        if (node->son[L])
        {
            ans = max(ans, run(node->son[L]));
            node->size += node->son[L]->size;
        }
        if (node->son[R])
        {
            ans = max(ans, run(node->son[R]));
            node->size += node->son[R]->size;
        }

        ans = max(ans, (long long)node->height * (long long)node->size);

        return ans;
    }
};


int h[MAXN];
int main()
{
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    while (n)
    {
        for (int i = 0; i < n; i++)
            cin >> h[i];

        CartesianTree *ct = new CartesianTree(h, n);

        cout << ct->run() << endl;

        cin >> n;
    }
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。