是时候学习笛卡尔树了

启示于2017 Multi—Contes Team 1 1012

笛卡尔树一种特定的二叉搜索树(Binary Search Tree) 适用于一般数列的RMQ, RtopkQ(区间第k大/小查询) 每个节点存有[key,value],从key来看的话每个节点的key大于其左孩子小于其右孩子,因此是二叉搜索树;从value来看具有堆的性质, 每个节点的value总是其子树value中的最值。利用笛卡尔树可以处理一些区间问题,只需将key与区间对应起来,所以说笛卡尔树还是相当的优雅的数据结构。
其中中序(inorder)遍历可以用来输出原序列。笛卡尔树的的建立可以采取复杂度为$O(n)$最右链式建法, 以建立小堆笛卡尔树为例。现
有序列$A[1…n]$, 取树根为A中最小的数的下标$i$,左子树为$A[1…i-1]$, 右子树为$A[i+1…n]$的笛卡尔树。(具体的建立使用栈来组织大小关系)

比如这样就建立了一颗小堆笛卡尔树。仔细观察的话还可以发现求$[l, r]$ 的最值相当于在树上找结点$l$到$r$的$LCA$ 下面的讨论将给出证明。

建立方法

遍历数组 把第一个值作为最初的根节点
(每个值从根节点出发一直向右走直到找到第一个比该值大的节点(或者走到无右子节点为止) 把该值放在找到的节点位置,原先位置的节点作为该值的左子节点)
或者从最右链由下往上出发找到第一个比该值小的数 p,将待插入的值作为p的右子节点,将p的原先的节点作为待插入值的左子节点
由于每个数最多进入一次最右链,最多一次退出最右链,因此均摊复杂度$O(n)$

Cartesian_Tree (C++)

[cpp]
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 10007;
const int inf = 0x3f3f3f3f;
const LL INF = (LL) 1<<62;
//int a[] = {0,9,3,7,1,8,12,10,20,15,18,5};
// int a[] = {0,4,7,9,2,1,3};
struct node {
LL value;
int index; //二叉堆第一关键词index, 第二关键词value
int pre, l, r;
void clear() {
l = r = pre = index =-1;
}
}T[maxn];
#define stack STACK
int stack[maxn];
pair<int,int> build(int n) {//建立笛卡尔树
int top = -1;
for (int i = 1; i <= n; i++) {//依次遍历数组元素
int k = top;
//while (k>=0 && a[stack[k]] > a[i]) k–;
//栈中比当前元素大的都出栈也就是找到第一个比待插元素小的数p

    while (k>=0 && T[stack[k]].value > T[i].value) 
        k--;//栈中比当前元素大的都出栈也就是找到第一个比待插元素小的数p
    if (k != -1) // 找到啦&&不是树根位置,此时这个a[i]成为栈顶元素的右孩子
        T[i].pre = stack[k], T[stack[k]].r = i;
    //这个值是树根位置或者要操作一般位置(栈内还有元素)
    if (k < top) //将stack[k]位置往下的节点变为a[i]的左孩子
        T[stack[k + 1]].pre = i, T[i].l = stack[k + 1];
    stack[++k] = i, top = k;//当前节点序号入栈,top指向栈顶序号
}
T[stack[0]].pre = -1;
return make_pair(stack[0], T[stack[0]].value); //返回根节点的序号和根节点的值

}
// Update from @霜刃未曾试
//另外一种O(n)构建笛卡尔树的方式,特点是代码很短
/int cartesian_build(int n) {
for(int i = 1; i <= n; i++) {
int k = i – 1;
while(tr[k].pri > tr[i].pri) k = tr[k].fat;
tr[i].son[0] = tr[k].son[1];
tr[k].son[1] = i;
tr[i].fat = k;
tr[tr[i].son[0]].fat = i;//很多人没加这句,父节点关系就会乱掉,
}//但到目前为止交到OJ上不会发生错误,因为此时这个点已不在最右链上,
return tr[0].son[1];不会用到其父节点了。
}
/
void inorder(int node) {//中序遍历可以还原序列
if(node==-1) return;
inorder(T[node].l);
printf(“%lld “,T[node].value);
inorder(T[node].r);
}
void level_order(int node) {//层次遍历
queue q; q.push(node);
while (!q.empty()) {
int k = q.front(); q.pop();
printf(“%lld “,T[k].value);
if (T[k].l != -1) q.push(T[k].l);
if (T[k].r != -1) q.push(T[k].r);
}
}
void DLR(int node) {//前序遍历
if(node == -1) return ;
printf(“%lld “,T[node].value);
DLR(T[node].l);DLR(T[node].r);
}
int main() {
int n;
while (scanf(“%d”, &n) != EOF, n) {
for (int i = 1; i <= n; i++)
scanf(“%lld”, &T[i].value), T[i].index = i, T[i].clear();
pair<int, int> root = build(n);
int root_value = root.second, root_index = root.first;
cout << “root’s value = ” << root_value << endl << “root’s index = ” << root_index << endl;
DLR(root_index);
}
}
[/cpp]

启示:有了这个方法后,我们可以发现一件显然的事:一个数列的RMQ即为他们在笛卡儿树上的 LCA!既然我们可以用O(n)-O(1) 的时间解决 LCA ,那同样就可以用O(n)-O(1) 的时间解决一般RMQ问题!

HDU 1605 Largest Rectangle in a Histogram


Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)(Java/Others)

Problem Description

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights $ 2, 1, 4, 5, 1, 3, 3$, measured in units where 1 is the width of the rectangles:

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.

Input

The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that $ 1 <= n <= 100000$.Then follow n integers h1, …, hn, where $ <= h_i <= 1000000000 $ . These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.

Output

For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.

Sample Input

[cpp]
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
[/cpp]

Sample Output

[cpp]
8
4000
[/cpp]

Source

University of Ulm Local Contest 2003

题解:

题目所求实则是找寻一段连续区间使得区间长度区间最小值最大,
我们可以利用笛卡尔树以读入顺序为第一关键词,读入的高为第二关键词且生成最小堆,
这样建的树因为总是从最下右链插入数字,
因此对于笛卡尔树的每个节点它总是小于其孩子结点且其和左右子树一并构成连续的区间,
这样只要我们按照二叉树的后续遍历,到达每个结点时更新最大值=左右子树子树规模
该结点对应的高(该连续区间最小的高)即可。总复杂度$O(n)$.

Code

[cpp]
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 100007;
struct node {
LL value;
int index;
int pre, l, r;
void clear() {l = r = pre = index =-1;}
}T[maxn];
#define stack STACK
int stack[maxn];
int build(int n) {
int top = -1;
for (int i = 1; i <= n; i++) {
int k = top;
while (k>=0 && T[stack[k]].value > T[i].value) k–;
if (k != -1)
T[i].pre = stack[k], T[stack[k]].r = i;
if (k < top)
T[stack[k + 1]].pre = i, T[i].l = stack[k + 1];
stack[++k] = i, top = k;
}
T[stack[0]].pre = -1;
return stack[0];
}
LL ans;
LL dfs(int node) {
if(node ==-1) return 0;
LL sz = dfs(T[node].l)+dfs(T[node].r)+1;
ans = max(ans,sz*T[node].value);
return sz;
}
int main() {
int n;
while(scanf(“%d”,&n)!=EOF,n){
for(int i = 1;i<=n;i++)
scanf(“%lld”,&T[i].value),T[i].index = i,T[i].clear();
ans = 0;
dfs(build(n));printf(“%lld\n”,ans);
}
}
[/cpp]

笛卡尔树(LCA)与RMQ的关系

参见2007国家队论文Day2 郭华阳《RMQ与LCA问题》点击查看

1.$RMQ​$=>$LCA​$考虑建立笛卡尔树的过程是不断划分最小值按照深度往大的方向建里
在建立的过程中,不断按照当前区间的最值来划分。
所以对于期间$[i,j]$的$RMQ$,我们同样可以这样来处理,对于处理好的笛卡尔树来说,每个区间的最小值都能很方便的得出。记整个区间的最小值的位置为$pos$,1@如果$pos$在$[i,j]$内的话这次$RMQ$就是pos对应的值,2@如果$pos<[i,j]$ 的话我们把整个区间的考量缩小到$[pos+1,N]$而这个区间的最小值按上述所说方便求取,2@如果$ pos>[i,j]$的话同$2$一样处理。如此发现求取$ RMQ$的过程与笛卡尔树建立的过程十分相似,而且我们每次总是一一的划分,所以这个过程就相当于求取$[i,j]$的公共祖先,而在求取的过程中最值的深度是由小变大的,因此这样不超过$O(logN)$次就能求的任意两点的$ LCA$,同时也是序列$[i,j]$的$RMQ$了;然而求取$RMQ$还有很多更加方便的方法因此了解即可。

2.$LCA$=>$RMQ$对于感觉这才是这二者比较精巧的地方,使用了$ Euler tour$的$ dfs$来记录欧拉序列,深度序列和每个节点出现的时间(时间戳);
对一棵树$ dfs$处理完成后由$ dfs$的性质对于节点$ u,v$,他们的$ LCA$一定出现在他们第一次出现的两个值的中间而且只出现一次,且是时间戳数组中$ pos[u]$~$ pos[v]$中深度最小的那个,至于为什么还是基于$ dfs$时的回溯必然要通过他们的祖先,在祖先中选取深度最小的即是他们的$ LCA$。

$LCA->RMQ$(算是改进普通$ ST+dfs$求解$ LCA$)有没有人能把我打醒(Update:已醒,看了论文百科瞎讲不对是我太弱)
[这个$O(n)-O(1)$的RMQ就是个分块,懂啦下一篇准备写个求$ LCA$的大杂烩解法包括Tarjan离线,树链剖分,平凡ST+dfs,线性ST+dfs,倍增算法]
区间$RMQ$即为他们在笛卡尔树上的$LCA$ (此处建议学习$ O(n)$的±1RMQ而非Sparse Table常见的$nlog(n)$)
我好菜 ±1-RMQ(约束RMQ)的$O(n)-O(1)$算法
求在线RMQ,根据原数列,建立笛卡尔树,线性规约成$LCA$问题,$ LCA$再线性规约成约束$ RMQ$,而约束$RMQ$通过线性在线解法,故整体复杂度 $O(n)-O(1)$

流程:

1.建立笛卡尔树 数组A在$[l,r]$上的最值等同于在笛卡尔最堆上下标为l,r的节点的$LCA$的值。
2.$LCA$转换为规约$RMQ$
对于规约RMQ采用dfs欧拉序+时间戳+深度数组($Eulur \ Tour$欧拉环游)
规约RMQ的解法分块+每块ST预处理$O(n)$ 对于查询分为块内查询+块间查询
对于块内查询由ST可$O(1)$得 对于块间类似$sqrt(n)$得分块查最值分为三块操作

$ ±1-RMQ$的 $< O(n)-O(1)> $ 求法

±RMQ 所谓约束RMQ就是序列种任意两个相邻数为±1,算法的核心在于分块的处理以$\displaystyle l=(\frac{log_2 N}{2})$的块把B序列划分成$ M=\frac{N}{l}$ 块,
设第k的最小值记为$ blockMin(k)$, $±RMQ$的最值就由三部分组成 $ block−RMQ \ and \ in−RMQ $
复杂度分析来看$ block-RMQ $的复杂度 $O(Mlog_2 M) − O(1)$
$\displaystyle Mlog_2 M =\frac{2N}{log_2 N}* log_2 M < \frac{2N}{log_2 N}*log_2 N = O(n)$

参考链接:

1.Topcoder RMQ ans LCA By danielp
2.演算法筆記 图论有很详细的图解
3.郭华阳,《2007国家队论文Day2——RMQ与LCA问题》
4.建國中學 2009/11/12程設講義 – LCA, RMQ, 笛卡爾樹 by su_horng


发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.