基于此paper ，我发现在O(lg N)中使用两个BITs来做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]的最小值，我们应该使用第二棵树而不是第一棵一;为了找到区间[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} .您有 [9..9] 的答案来自 BIT1以CLB2的第一个成员.你有 [11..11] 的答案来自 BIT2 , 取 CLB1 的第一个成员. {10}和 {12}是微不足道的。
16 - 你需要查询[1..9] . {10} , [11..15] (没有 {16} 因为它是虚构的)。您正在服用 [1..9]来自 BIT1取 CLB2 的前两项.您正在服用 [11..15]来自 BIT2取 CLB1 的前两项. {10}是微不足道的。
如您所见，对于左侧查询，您使用 p-1 中的攀登历史从第一棵树中获取答案。第二棵树的。对于正确的查询，您可以使用 p+1 的攀登历史从第二棵树中获取答案。第一棵树。
类似的过程用于更新正确的树。
更新:第 9 个节点的进程
在更新第 9 个索引的情况下，我们有下一个 CLB小号:
CLB1 : {10, 12} ，间隔:[10..11] , [12..15]的 BIT2 .
CLB2 : {8} ，间隔:[1..8]的 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}
关于algorithm - RMQ使用两个fenwick树(二叉索引树)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42685826/