怎么建这个order-statistic tree

CougarHead
obduracy 2011-01-07 字数 1404

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

看下面的解答不懂这个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)).

Algorithm 算法
10 个回复
justicezyx
又跑路在即 2011-01-07

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

CougarHead
obduracy 2011-01-07

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

能否给个例子?

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

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

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

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

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

justicezyx
又跑路在即 2011-01-08

不知道

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

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

: 能否给个例子?

wywcgs
乌鸦 2011-01-08

Largest Rectangle in a Histogram?

看着好眼熟。

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

的啊,用不着建什么树。

给个核心代码段:

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

meixr
一条大河波浪宽 2011-01-09

貌似以前看过,想不起来了,为啥O(n)

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

: Largest Rectangle in a Histogram?

: 看着好眼熟。

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

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

CougarHead
obduracy 2011-01-09

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

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

谢谢大家了

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

: Largest Rectangle in a Histogram?

: 看着好眼熟。

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

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

wywcgs
乌鸦 2011-01-09

真愁人. 您稍微动下脑子想想再说话行不?

最大矩形的高度一定等于其中某单独元素的高度,否则的话其高度必然可以再增加.

所以我们枚举它究竟是哪个元素的高度, 然后我们看它在这个元素的位置上时 向左右

最多到底能扩展到多远.

向左扩展的最远点,就是左面第一个比它小的元素; 向右扩展的最远点, 就是右面第一

个比它大的元素. 然后就是我的说那些东西. 我就是说了下核心部分, 劳烦您花点时间

稍微扩展下行不?

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

另外, 上面那个什么ordered-statistic tree, 不过就是类似的方法.

本质上就是先找到这个序列里面高度最小的元素, 因为它就是高度最小的,所以不会碰

到任何障碍. 所以可以以它为高度扩展到整个序列, 得到一个candidate,记录一下. 然

后如果不以它为高度, 那么它必然把整个序列分成左右两部分, 用d&c分别处理两个部

分就好了.

然后你会发现, 整个过程你需要做的东西, 就是快速的知道区间[a, b)内最小的元素是

多少/在哪里, 那个什么os tree, 就是一个类似于interval tree的无聊东西, 记录下

区间最小值和位置就行了.

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

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

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

: 谢谢大家了

wywcgs
乌鸦 2011-01-09

对循环内每个单独的i, 考虑i, left[i], left[left[i]], ......, left^(k)[i], -1.

会发现这个序列的长度每次必然增加1, 但是减少的长度不定. 第二重循环每运行一次, 长

度就减少1.

由于这个序列n次必然增加长度n,所以n次减少的总次数必然小于等于n, 也就是说第二重循

环总共最多运行n次, 总的复杂度是O(n).

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

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

wywcgs
乌鸦 2011-01-09

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

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

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

间. 也就是说如果父节点是[x, y), 它的左儿子就是[x, (x+y)/2 ), 右儿子就是

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

然后你在每个节点里面记录下这个节点所代表的区间的一些信息, 比如说这道题就是纪

录着这个区间内最小元素的大小/位置.

每次查询一个的时候,从根节点开始查询. 然后每次判断待查询区间是否覆盖了当前节

点 所代表区间的全部. 如果覆盖了, 那么直接取用这个节点记录下来的那些信息, 不

用再去遍历了; 否则的话, 就要分别对其左右儿子( 也就是左右半 )进行查询, 最后再

把结果汇总起来.

自己去想想, 这种做法最后每次查询的复杂度是O(lgn).

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

wxstorm
企鹅 2011-01-09

拜~~~~大~~~~~~~牛~~~~~~~

做算法抱佛脚大脑一片混乱中

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

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

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

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

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