计算最大子段数的算法

Question

给定一个包含 n 个整数值段的向量，我正在搜索 O(n log n) 算法来计算包含大多数其他段的段。事实上，我只对这些分割市场的数量感兴趣。

我尝试过线段树和区间树的变体，但没有一个是相关的。我遇到的真正问题来自部分订单。如果顺序是全序的，直接计算包含树问题会容易得多。

示例:a = [4;11] b = [2;7] c = [5;8] d = [6;7] e = [3;9] f = [1;10] g = [10;42]

这里我们有包含 e c b 和最大的 d 的 f。当然，g 长得多，但不包含任何其他段，所以这不是最大段的问题。

我们可以显示顺序图(传递弧未显示):

f -----> b  ---> d
  \-->e--->c-/
       a-/
g

对我来说主要的问题是我不能在处理段时排除 a ，因为在某些时候可能会出现 f 中未包含的子段并使 a 成为最大的段。

Answer 1

O(n log n) 是可能的(我假设开区间并且没有端点重叠)

您将所有端点排序到一个排序列表(升序)中，并跟踪哪个区间(比如使用 id)以及特定点是区间的哪一端。

现在您维护一个支持以下内容的数据结构:

AppendAtEnd(interval_id)
int GetPosition(interval_id)
Value Remove(interval_id)
IncrementValuesLessThanPosition(j)

这是一个结构，它接受一个键 (intervals_ids) 并维护一个有序的(按插入时间)列表，还有一个初始值为 0 的附加值，我们用它来跟踪子间隔。

它允许你在末尾插入。使用 id 删除(并获取相应的值)，获取 id 的位置(如果它是使用链表实现的，可以将其视为与头部的距离)并递增列表的特定前缀的所有值。

为了将此结构用于我们的问题，我们遍历上面的排序列表，每次看到区间的左端点时，我们调用 AppendAtEnd。

每次我们看到一个区间的右端点，我们得到它的位置，我们删除它，并增加所有小于该位置的值(基本上所有将这个删除的区间作为子区间的区间)。

使用具有适当装饰信息(如子树总和和节点计数)的平衡树，这是可行的，因此每个操作都是 O(log n)。