具有范围交集的线段树

Question

最近我在思考一个爱好项目时遇到了一个范围问题。

考虑一个从 0 开始索引、大小为

A

("[0, A)") 的大二进制数组，我想支持 3 个范围（范围定义为“[左，右）”，但不是很重要并且可以按需更改）操作：

1. RangeSet(v, left, right)

   将范围设置为一个值。例如，

   00000

   之后的

   RangeSet(1, 1, 3)

   将是

   01100

   。

2. RangeIntersectQuery(left, right)

   查找某个范围与数组中所有 1（或 0）之间的交集，然后将结果合并到范围列表中。例如，

   RangeIntersectQuery(1, 5)

   上的

   011010010

   将是范围

   ([1, 3), [4, 5))

   的列表。我不确定范围的顺序将来是否重要，但列表可能会降级为无序集合。

3. RangeQuery(left, right)

   检查间隔是否充满 1 秒（或 0 秒）。例如，

   RangeQuery(3, 5)

   上的

   00010110

   为 false，而

   RangeQuery(5, 7)

   为 true。

理想情况下，所有操作只涉及 1，但支持 0 应该不会造成太大麻烦。

我认为线段树应该能够在

O(logA)

时间和

O(k*A)

总内存中解决操作1和3。但是，我很难想出处理操作 2 的好方法。

A

最多可达 10^9。

RangeSet

的范围长度可能最多为 10^3。

RangeQuery

的长度大概是10^6-10^7左右。

RangeIntersectQuery

的长度应该在10^8-10^9左右。我真的不想在 3 个操作上花费

O(A)

时间，我希望它们是次线性的。

我正在寻找一种可以解决我的问题的算法/数据结构。

Answer 1

这里有一个不同的想法：将二进制数组编码为二进制函数，将索引（解释为二进制变量数组）映射到布尔值，将该函数表示为ROBDD（从现在开始我将只写BDD 并暗示它将被减少和排序，即 ROBDD）。

RangeSet(1, l, r)

变为：创建范围谓词

l <= index < r

的 BDD（这总是会产生具有 O(log A) 个节点的小型 BDD），并将其与编码二进制数组的 BDD 进行“或”操作。

RangeIntersectQuery

：再次从创建范围谓词开始，然后将谓词 BDD 与数组 BDD 进行 AND 操作。结果是一个 BDD，它对范围内设置的条目进行编码。虽然这不是范围列表，但它是表示交集的一种相当灵活的方式 - 您可以有效地对该 BDD 执行各种操作（根据该 BDD 的大小而不是条目数及时计算 True 条目，或者整个结果到另一个 BDD 中，其他东西），但也只是枚举所有 True 条目（如果这是您想要做的）。

RangeQuery

：一种方法是使用

RangeIntersectQuery

，然后计算交集中有多少 True 条目（有一个简单的算法可以缩放表示交集的 BDD 节点数量） ，将其与范围的大小进行比较。作为一种快捷方式，您可以否定范围谓词并将其与数组 BDD 或，然后您将得到简单的 BDD ⊤ iff 查询的范围完全为 True，无需计数。

对于所有这些事情（你可以做更多），速度主要取决于 BDD 的大小（节点数量），而不是直接取决于

A

，当然节点数量只能很大如果

A

很大。如果数组的内容非常混乱，则对数组进行编码的 BDD 会很大，但如果它有某种顺序，则 BDD 通常不会很大，但有一些例外，其中顺序可以描述但无法捕获BDD 的缩减机制。