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