# 怎么建这个order-statistic tree

Initially, build a binary, node- and leaf-labeled tree that contains the histogram as its frontier, i.e., as its leaves from left to right. Mark each inner node with the minimum of the labels of its subtree. Note that such a tree is most efficiently stored in an array using the heap data structure, where the children of node i are located at positions i*2 and i*2+1, respectively. With such an order-statistic tree, the minimum element in a subhistogram (i.e., a subsegment of the sequence of heights) can be found in O(log(n)) steps by using the additional information in the inner nodes to avoid searching all leaves.

To calculate the maximum rectangle unter a subhistogram, we thus find the minimum height in that subhistogram, and divide it at just that place into two smaller histograms. The maximum rectangle is either completely in the left part, or completely in the right part, or it contains the rectangle with minimum height. The first two cases are solved recursively, while in the third case we know that the width of the maximum rectangle is the width of the whole subhistogram, since we chose the minimum height. Because every element serves exactly once as a place to divide, and we spend O(log(n)) for every division, the complexity of this algorithm is O(n*log(n)).

10 个回复

http://pine.cs.yale.edu/pinewiki/OrderStatisticsTree

contains the histogram as its frontier, i.e., as its leaves from

left to right. Mark each inner node with the minimum of the labels

of its subtree. Note that such a tree is most efficiently stored in

an array using the heap data structure, where the children of node

i are located at positions i*2 and i*2+1, respectively. With such

an order-statistic tree, the minimum element in a subhistogram

(i.e., a subsegment of the sequence of heig: ...................

【 在 CougarHead (obduracy) 的大作中提到: 】

: 比较经典的一个算法问题，Largest Rectangle in a Histogram

: 看下面的解答不懂这个tree到底是什么样子的。哪个给讲解一下？多谢!

: Initially, build a binary, node- and leaf-labeled tree that

【 在 justicezyx (inception好) 的大作中提到: 】

http://pine.cs.yale.edu/pinewiki/OrderStatisticsTree

: 话说我上次还看过，这会儿就给忘了。。。

: contains the histogram as its frontier, i.e., as its leaves from

: ...................

【 在 CougarHead (obduracy) 的大作中提到: 】

: 话说光看这个还是不知道这个树长得啥样啊

: 能否给个例子？

Largest Rectangle in a Histogram?

for(int i = 0, j; i < n; i++) {

for(j = i-1; j >= 0 && a[j] >= a[i]; j = left[j]);

left[i] = j;

}

histogram as its frontier, i.e., as its leaves from left to right. Mark each

inner node with the minimum of the labels of its subtree. Note that such a

tree is most efficiently stored in an array using the heap data structure,

where the children of node i are located at positions i*2 and i*2+1,

respectively. With such an order-statistic tree, the minimum element in a

subhistogram (i.e., a subsegment of the sequence of heig:

...................

【 在 CougarHead (obduracy) 的大作中提到: 】

: 比较经典的一个算法问题，Largest Rectangle in a Histogram

: 看下面的解答不懂这个tree到底是什么样子的。哪个给讲解一下？多谢!

: Initially, build a binary, node- and leaf-labeled tree that contains the

【 在 wywcgs (乌鸦) 的大作中提到: 】

: Largest Rectangle in a Histogram?

: 看着好眼熟。

: 如果你是要对序列中的每个数，找到他左面/右面第一个比他小的数， 这个是可以O(n)

: ...................

【 在 wywcgs (乌鸦) 的大作中提到: 】

: Largest Rectangle in a Histogram?

: 看着好眼熟。

: 如果你是要对序列中的每个数，找到他左面/右面第一个比他小的数， 这个是可以O(n)

: ...................

---------------------------

【 在 CougarHead (obduracy) 的大作中提到: 】

: 注意：要求的是面积，你这都没有出现

: 另外，我不是想知道O(n)的方法，而是想看一下怎么用这个os tree的办法来做。

: 谢谢大家了

【 在 meixr ()毛茸茸（) 的大作中提到: 】

: 貌似以前看过，想不起来了，为啥O（n)

interval tree的每个节点都代表着一个区间. 根节点是总区间[0, n),然后任何一个节

[(x+y)/2, y).

histogram as its frontier, i.e., as its leaves from left to right. Mark each

inner node with the minimum of the labels of its subtree. Note that such a

tree is most efficiently stored in an array using the heap data structure,

where the children of node i are located at positions i*2 and i*2+1,

respectively. With such an order-statistic tree, the minimum element in a

subhistogram (i.e., a subsegment of the sequence of heig:

...................

【 在 CougarHead (obduracy) 的大作中提到: 】

: 比较经典的一个算法问题，Largest Rectangle in a Histogram

: 看下面的解答不懂这个tree到底是什么样子的。哪个给讲解一下？多谢!

: Initially, build a binary, node- and leaf-labeled tree that contains the

【 在 wywcgs (乌鸦) 的大作中提到: 】

: 好吧, 或许您可能连interval tree是什么都不知道, 那就再说说.

: interval tree的每个节点都代表着一个区间. 根节点是总区间[0, n),然后任何一个节

: 点都有左右两个儿子, 左儿子代表着父节点的左半区间, 右儿子代表父节点的右半区

: ...................