根据这篇论文，我发现使用两个 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] 的最小值，我们应该使用第一棵树。

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

对于给定的整数数组，我们必须XORed在给定的范围内计算总和[L, R]，XORed总和是指Σ(Arr[i]^p)在哪里i:[L,R]和p是某个数字。这可以在计算从数组开头到数组中XORed每个元素的总和时轻松完成。i-th现在，当p更改非常频繁时，就会出现问题。在这种情况下，重新计算XORed总和直到每个i-th元素似乎都不是理想的解决方案。我想这可以使用fenwick treeor来完成BIT。但我无法弄清楚如何处理fenwicktree 或BIT. 任何帮助，将不胜感激。

我试图解决这个算法问题，我遇到了这个很好的解决方案：

“我们的想法是不对称地对待 a _i、 b _i和 c _i。BIT 支持从 1 开始的键间隔的最小查询。我们使用 c _i作为值和 b _i作为键。这些按增加 a 的顺序插入_i . 这样，对于每个 a _{i ，数据结构允许查询 c j}的最小值（可能是 ∞ ）在 [1..b _{i中的 b j}和 a _j < a _i。我们有 c _j < c _i当且仅当参赛者 i 不优秀时。”

来源

现在我很难理解这个解决方案。

这是我对这个解决方案的理解：我知道二叉索引树用于回答查询，例如在数组中查找区间的总和，它还支持元素更新。它分别以 O(logn) 时间复杂度执行这两项操作。现在这个解决方案说我们用键作为 c _i和值作为 b _i构建 BIT ，这基本上是 b _i是每个节点的附加值。现在我们在树中插入_i值增加的元素，这就是我失去控制的地方。我们插入节点的顺序以及该部分后面的语句所说的内容有什么关系，我不知道。

请帮助我了解此解决方案的含义。

我想使用 Fenwick 树对字符串进行范围查询。但是我的代码出了点问题。连接给出错误 Eror is:[Error] no match for 'operator+=' (operand types are 'std::vector >' and 'std::string {aka std::basic_string}') 给定一个字符串 s，我想要将字符串存储在这棵芬威克树中。例如 s=abcdef，在 BIT 上它应该像（上-下）a ab-c abcd-e abcd-ef 树结构

我在互联网上搜索，但找不到一个好的。我从 geeksforgeeks.org 获得了一些帮助，但无法理解我们在更新 BIT 数组时从 aux[i][j] 中减去 v1-v2-v2-v4+v3 的构造部分。让我知道为什么我们在这里减去。

给定数组中的反转计数非常有名，时间复杂度为 O(NlogN)。但是，我想知道是否有办法通过更新来做到这一点。输入格式：第一行由整数 n 组成；第二行包括 n 个整数，它是数组 下一行包括 m 更新的数量接下来的 m 行有整数，x 和 y。您必须将索引 x 处的数字更新为 y 并输出反转数。输出：输出由 m 行组成。每个更新/查询一个整数

有谁能帮我解决（#no离线编程）？

问题

我有一个包含 N 个数字的数组。这些数字可能是不同的，也可能是无序的。我必须回答关于 A 和 B 之间有多少不同数字的 Q 查询。其中 A、B 是 0 <= A <= B < array.Length 之间的索引。

我知道如何通过使用 HashTable 来完成每个查询的 O(N)，但我要求更有效的解决方案。我试图通过 sqrt 分解和分段树来改进它，但我做不到。我没有显示任何代码，因为我没有找到任何可行的想法。我正在找人解释更快的解决方案。

更新

我读到您可以收集查询，然后使用二进制索引树 (BIT) 来回答所有问题。有人可以解释如何做到这一点。假设我知道 BIT 是如何工作的。

二叉索引树和二叉搜索树是一回事吗？如果不是，它们之间的实际区别是什么以及何时使用什么？

问题：

我有 n 个向量的输入：

任务是计算输入中的最小向量。

资源：

我在本地编程竞赛的任务中发现了这个问题。

（翻译后的）公式是：

1<=n<=100000 时间限制：1 秒。

我的尝试和想法

第一个想法是创建类 Result（用于竞争对手的结果），重载运算符 >（或 <），就像：

并构建任何基于数组（例如最小堆），允许找到最小值（使用<）并计算它们（我认为我只是按照这种方式“重新创建”了堆排序的错误变体）。在我这次尝试失败后，我尝试了 Fenwick 树（二进制索引树）来完成相同的任务。

但是后来我明白我的方法是不正确的（不是 ok 类和 < 重载），并且将任务转换为 1d 的想法根本不好。

然后我找到了一些关于 BIT & Segment Tree for n-dimensions case 的信息，我认为我可以用它们来解决这个问题。但是我很难实现工作变体（甚至在 1d 内理解段树的工作原理）

也许有人可以帮助实施（或找到更好的解决方案并解释它）？

我的问题涉及二进制索引树（Fenwick Trees）中更新步骤背后的全部原因。因此，当以特定增量更新我们的数组时，在特定位置，更新如下所示：

我的问题是index += index & (-index);零件。请注意，我理解这index & (-index)一点，尤其是在查询树的上下文中。

我已经使用此索引更新规则手动尝试了几个示例，但我无法找到添加背后的逻辑index & (-index)，以便转到下一个需要更新的节点。

从我起床到这一点，iBIT 中的一个节点对数组中的原始值“负责”，范围为[i - i & (-i) + 1, i]，因此这意味着任何节点都将落入这种形式的范围内。具体来说，据我了解，当想要更新k原始数组中的位置时，我们遵循以下步骤（从概念上讲，不是在实际代码中）：

• 迭代0：更新BIT[k + 1]（索引1在 BIT 数组中移动）。在迭代0时，我们更新了我们正在查看的索引，所以我假设我们正在寻找负责 node 的下一个最小间隔k，因此我们需要找到下一个索引iwhere i - i & (-i) < k < i。i通过将当前索引增加 来查找此索引k & (-k)。

其余的迭代以相同的方式发生，直到我们超出限制。我已经手动尝试了许多示例，但我仍然不明白为什么添加i & (-i)会将我们带到正确的下一个节点。我在网上找到的每一个教程，包括视频，在这件事上都是完全不靠谱的。

这里有几个关于BITs的相关问题，请不要在仔细阅读之前将它们与我的合并。据我所知，这个特定的问题尚未得到解答。