树的二三事(二)

一、树的多种分身

类型	内容
二叉树	二叉树· 二叉搜索树 (BST) · 笛卡尔树 · Splay Tree · Link Cut Tree · Top Tree · T树
自平衡二叉查找树	AA树 · AVL树 · 红黑树· 伸展树· 树堆 ·节点大小平衡树
B树	B树· B+树 · B*树 · Bx树 ·UB树 · 2-3树 · 2-3-4树 ·(a,b)-树 · Dancing tree · H树
Trie	前缀树 · 后缀树· 基数树
空间划分树	四叉树· 八叉树· k-d树 · vp-树 · R树 · R*树 · R+树 · X树 · M树 · 线段树· 希尔伯特R树 · 优先R树
非二叉树	Exponential tree ·Fusion tree ·区间树 ·PQ tree ·Range tree ·SPQR tree ·Van Emde Boas tree
其他类型	堆 · 散列树 ·Finger tree ·Metric tree ·Cover tree ·BK-tree ·Doubly-chained tree ·iDistance ·Link-cut tree ·树状数组

二、二叉树

1、二叉搜索树(BST)

二叉搜索树BST比较简单，给出其定义及特点即可。
假设有一个二叉搜索树T，给定任意任意节点N，都满足N大于其左子节点，小于其右子节点

基于这个特征，BST的中序遍历即是节点Value从小到大的遍历

2、笛卡尔树Cartesian Tree

笛卡尔树是一种特殊的二叉搜索树，其有两个特征
1. 任意节点的秩均大于左子节点的秩，小于右子节点的秩
2. 任意节点的值均小于其子节点的值

性质一等同于将其秩作为构建条件，满足了二叉搜索树BST的特点(BST用值作为构建条件)，将笛卡尔树中序遍历的结果
即是其用于构建时的原数组。

性质二等同于小顶堆的特点。

引入笛卡儿积的构建过程：
1. 从第一个元素开始，从左往右遍历数组L
2. 将第一个元素作为树的根节点R
3. for i in [a[1], a[2]…a[n]]
4. 如果a[i]小于其根节点R，则将a[i]作为根节点R的父节点(R成为a[i]的左子树，类似于zig旋转)
5. 如果a[i]大于其根节点R，则将a[i]从根节点的右节点开始寻找位置(未到达外部节点的临界，遵循步骤4，若到达外部节点临界仍大于当前比较节点，则成为其右子节点)

引入笛卡尔树的应用：

HDU 1506

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 0 <= hi <= 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