4

假设我们希望跟踪一组区间中的最大重叠点——数据库中与它重叠的区间数最多的点。

一种。表明总会有一个最大重叠点，它是其中一个线段的端点。

湾。设计一个有效支持操作 INTERVAL-INSERT、INTERVAL-DELETE 和 FIND-POM 的数据结构，该操作返回最大重叠点。（提示：保留所有端点的红黑树。将 +1 值与每个左端点相关联，并将 -1 值与每个右端点相关联。用一些额外信息来扩充树的每个节点以维护最大重叠点。）

这个问题在《算法介绍》一书中。但我不知道如何解决第二个问题。如果一个更伟大的头脑有一个优雅的解决方案，请与我分享你的想法！谢谢。

4

1 回答 1

4

引用：http ://ripcrixalis.blog.com/2011/02/08/clrs-chapter-14/

保留所有端点的 RB 树。我们将端点一一插入，作为从左到右扫描的扫描线。对于每个左端点 e，关联一个值 p[e] = +1（将重叠增加 1）。与每个右端点 e 关联一个值 p[e] = -1（将重叠减少 1）。当多个端点具有相同的值时，请先插入具有该值的所有左侧端点，然后再插入具有该值的任何右侧端点。

这是一些直觉。让 e1, e2, . . . , en 是与我们的区间相对应的端点的排序序列。让 s(i, j) 表示总和 p[ei] + p[ei+1] + · · · + p[ej]，其中 1 ≤ i ≤ j ≤ n。我们希望找到一个最大化 s(1, i ) 的 i。每个节点 x 存储三个新属性。我们存储 v[x] = s(l[x], r [x])，即 x 的子树中所有节点的值的总和。我们还存储 m[x]，即通过表达式 s(l[x], i) 对任何 i 获得的最大值。我们将 o[x] 存储为 m[x] 达到最大值的 i 的值。对于哨兵，我们定义 v[nil[T]] = m[nil[T]] = 0。

我们可以以自下而上的方式计算这些属性以满足定理 14.1 的要求：

v[x] = v[left[x]] + p[x] + v[right[x]] ,
m[x] = max{
m[left[x]] (max is in x’s left subtree),
v[left[x]] + p[x] (max is at x),
v[left[x]] + p[x] + m[right[x]] (max is in x’s right subtree). }

一旦我们了解了如何计算 m[x]，就可以直接从 x 及其两个子项中的信息计算 o[x]。

FIND-POM：返回其端点由 o[root[T]] 表示的区间。由于我们如何定义新属性，定理 14.1 说每个操作在 O(lg n) 时间内运行。事实上，FIND-POM 只需要 O(1) 时间。

于 2013-07-09T04:59:14.953 回答