基于这篇论文，我发现在O(lg N)中使用两个 BIT 来做 RMQ 是非常聪明的，因为它比段树更容易编码，并且论文声称它的性能也比其他数据结构更好。
我了解如何构建树以及如何执行查询操作，但我对更新操作感到困惑。以下是引述：
我们进行以下观察：当我们生成相关的间隔 我们经过的节点，我们可以从节点开始覆盖整个区间[ p + 1， y]p + 1 并爬上第一棵树(图 2.1)。因此，我们不是对每个节点进行查询，而是 更新，我们通过爬树一次来动态计算查询的结果。
类似地，我们可以更新表单[ x， p – 1]的所有间隔，方法是从 节点 p – 1 并爬上第二棵树(图 2.2)。相同的算法应用于 更新两棵树。
我怀疑它应该是相反的：为了找到最小区间[p+1， y]，我们应该使用第二棵树而不是第一棵树;为了找到最小区间[x， p-1]，我们应该使用第一棵树。
我的问题是：我说得对吗？如果没有，有人可以举一个简单的例子来演示更新操作的工作原理吗？
解释有点模棱两可。我猜他们的意思是，对于[p+1,y]，您从p+1开始攀登前三个，但使用第二棵树进行查询。
假设您在第 10 个索引(来自论文)处更新值。在更新树时，您必须回答[x, 10 - 1]和[10 + 1, y]的查询。为了有效地做到这一点，你建立了两个"攀登"列表：
CLB1从p+1：{11, 12}爬上第一棵树，对应于第二棵树的下一个间隔：[11..11]，[12..15]
CLB2爬上第二棵树，从p-1：{9, 8}，对应于下一个间隔：[9..9]，第一棵树的[1..8]
现在，您通过爬上从 10 开始的第一棵树来开始更新第一棵树。
10 - 简单更新
12 - 需要查询[9..9]、{10}、[11..11]、{12}。您可以通过CLB2的第一个成员从BIT1中[9..9]答案。并且您通过获取CLB1的第一个成员，从BIT2中[11..11]有一个答案.{10}和{12}都是微不足道的。
16 - 您需要查询[1..9]。{10}，[11..15](没有{16}因为它是虚构的)。您通过获取前两项CLB2从BIT1中获取[1..9]。您通过服用前两项CLB1从BIT2中获取[11..15]。{10}是微不足道的。
正如您在左侧查询中看到的，您可以使用第二棵树p-1的攀爬历史记录从第一棵树中获取答案。对于正确的查询，您可以使用第一棵树p+1的攀爬历史从第二棵树中获取答案。
类似的过程用于更新正确的树。
更新：第 9 个节点的进程
在更新第 9 个索引的情况下，我们有下一个CLBs：
CLB1：{10, 12}， 间隔：[10..11]，BIT2的[12..15]。
CLB2：{8}， 间隔：BIT1的[1..8]
更新BIT1：
9 - 琐碎
10 - 琐碎(我们只需要{9}和{10})
12 - 我们需要从CLB1-[10..11]首次输入，并与{9}{12}
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}的第一个条目