RMQ使用两个fenwick树（二叉索引树）
RMQ using two fenwick trees (binary indexed tree)
基于这个paper，我发现在O(lg N)中用两个BIT来做RMQ是相当高明的，因为它比线段树更容易编码，并且论文中声称它性能也优于其他数据结构。
我知道如何构建树以及如何进行查询操作，但我对更新操作感到困惑。引用如下：
We make the following observation: when we generate the associated intervals of
the nodes we pass by, we can cover the whole interval [ p + 1, y ] by starting from node
p + 1 and climbing the first tree (Fig. 2.1). So instead of doing a query for every node we
update, we compute the results of the queries on the fly by climbing the tree once.
Analogously, we can update all the intervals of the form [ x, p – 1] by starting from
node p – 1 and climbing the second tree (Fig. 2.2). The same algorithm is applied for
updating both trees.
我怀疑应该反过来：为了找到区间 [p+1, y] 的最小值，我们应该使用 second tree代替第一个；为了找到区间 [x, p-1] 的最小值，我们应该使用 第一棵树 代替。
我的问题是：我说得对吗？如果不是，有人可以举一个简单的例子来演示更新操作是如何工作的吗？
解释有点含糊。我猜他们的意思是，对于 [p+1,y]，您从 p+1 开始攀登前三棵树，但使用第二棵树进行查询。
假设您更新第 10 个索引处的值（来自论文）。在更新树时，您将必须回答 [x, 10 - 1] & [10 + 1, y] 的查询。为了有效地做到这一点，您构建了两个 "climbing" 列表：
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], [12..15] of BIT2.
CLB2：{8}，间隔：[1..8] of BIT1
正在更新 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}
的第一个条目
基于这个paper，我发现在O(lg N)中用两个BIT来做RMQ是相当高明的，因为它比线段树更容易编码，并且论文中声称它性能也优于其他数据结构。
我知道如何构建树以及如何进行查询操作，但我对更新操作感到困惑。引用如下：
We make the following observation: when we generate the associated intervals of the nodes we pass by, we can cover the whole interval [ p + 1, y ] by starting from node p + 1 and climbing the first tree (Fig. 2.1). So instead of doing a query for every node we update, we compute the results of the queries on the fly by climbing the tree once.
Analogously, we can update all the intervals of the form [ x, p – 1] by starting from node p – 1 and climbing the second tree (Fig. 2.2). The same algorithm is applied for updating both trees.
我怀疑应该反过来：为了找到区间 [p+1, y] 的最小值，我们应该使用 second tree代替第一个；为了找到区间 [x, p-1] 的最小值，我们应该使用 第一棵树 代替。
我的问题是：我说得对吗？如果不是，有人可以举一个简单的例子来演示更新操作是如何工作的吗？
解释有点含糊。我猜他们的意思是，对于 [p+1,y]，您从 p+1 开始攀登前三棵树，但使用第二棵树进行查询。
假设您更新第 10 个索引处的值（来自论文）。在更新树时，您将必须回答 [x, 10 - 1] & [10 + 1, y] 的查询。为了有效地做到这一点，您构建了两个 "climbing" 列表：
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], [12..15] of BIT2.
CLB2：{8}，间隔：[1..8] of BIT1
正在更新 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}