使用两个fenwick树（二叉索引树）的RMQ

Question

基于此paper，我发现在O(lg N)中使用两个BIT来完成RMQ是相当出色的，因为它比段树更容易编码，而且该文章声称它性能也比其他数据结构好。

我明白如何构建树以及如何执行查询操作，但我对更新操作感到困惑。这里的报价：

我们做出以下观察：当我们生成的 节点相关联的时间间隔我们路过，我们可以覆盖整个间隔[P + 1，Y]通过从节点 开始p + 1和爬第一棵树（图2.1）。因此，我们不需要对每个节点进行查询，而是更新我们的 ，我们通过一次爬树来即时计算查询结果。 [ - 1，X，P]通过从 节点p开始 -

类似地，我们可以更新形式的所有时间间隔1和攀登第二树（图2.2）。 同时更新两棵树。

我怀疑它应该是倒过来：用于找到的最小间隔[P + 1，Y]，我们应该使用第二树代替所述第一个的;为找到最小间隔[x，p-1]，我们应该使用第一棵树代替。

我的问题是：我是否正确？如果不是，有人可以举一个简单的例子来演示更新操作的工作方式吗？

Answer 1

该解释有点含糊。我想他们的意思是[p+1,y]你从p+1开始爬上前三个，但用第二个树来查询。

让我们假设您更新第10个索引的值（来自纸张）。在更新树时，您必须回答[x, 10 - 1] & [10 + 1, y]的查询。为了有效地做到这一点，你建两个“爬”名单：

CLB1由p+1攀爬第一棵树：攀登[11..11]，第二棵树

CLB2的[12..15]：{11, 12}，其对应于下一个区间从p-1第二棵树：{9, 8}，其对应于下一个时间间隔：[9..9]，第一棵树

现在你开始第一树通过爬上第一棵树STA更新的[1..8]与10

10 rting - 平凡的更新

12 - 您需要查询[9..9]，{10}，[11..11]，{12}。通过参加CLB2的第一个成员，您可以从BIT1获得[9..9]的答案。并通过CLB1的第一个成员从BIT2获得[11..11]的答案。 {10}和{12}是微不足道的。

16 - 您需要查询[1..9]。 {10},[11..15]（没有{16}，因为它是虚构的）。您从BIT1拍下[1..9]，拍下前两项CLB2。您拍下[11..15]，从BIT2开始，拍下前两项CLB1。 {10}是微不足道的。

正如你可以看到左边的查询你从第二棵树的p-1使用攀爬历史记录中的第一棵树得到答案。对于正确的查询，您可以使用第一棵树的p+1的攀登历史记录从第二棵树中获取答案。

类似的过程用于更新右树。

更新：过程第九节点

在更新9日指数情况下，我们有下一个CLB S：

CLB1：{10, 12}，间隔：[10..11]的BIT2[12..15]。

CLB2：{8}，间隔：的BIT1

[1..8]更新BIT1：

9 - 琐碎

10 - 琐碎（我们只需要{9}和{10}）

12 - 我们需要来自CLB1的第一项 - [10..11]和{12}与{9}

16 - 我们需要CLB1两个第一项 - [10..11] U [12..15]，从CLB2第一个条目 - [1..8]和{9}

更新BIT2：

9 - 平凡

8 - 我们需要先CLB1 - [10..11] U [12..15]和{9}两个条目与{8}

0 - 我们需要CLB1前两个条目 - [10..11] U [12..15]和CLB2第一项 - [1..8]和{9}