问题标签 [fenwick-tree]

我已经阅读了一些关于二进制索引树的教程，但是当查询和更新两个操作都在某个范围内时，我无法理解如何实现它。

这个问题是由 codechef 中的travtree问题引起的。在社论DFS中，他们建议通过在遍历中记录每个节点的发现和退出时间，将树线性化为数组。现在我们可以通过汇总该节点sum subtree段中发生的事件来快速回答有关- 的查询。[discovery time, exit time]（我们使用Fenwick树来快速回答这些查询）。

然而，为了解决这个问题，我们还需要快速回答sum path查询。也就是对沿最短路径发生的事件求和a, b。这怎么可能？他们给出的答案是这样的：

对于每个有趣的事件，他们都会更新：

现在sum path(a,b)是这样的：

query前缀总和在哪里。怎么正确？？当您查看前缀总和时，您可能会遇到许多与和a之间的路径无关的节点！la

我有一个 Fenwick 树的以下实现来解决 HackeEarth 上的以下问题。

我的解决方案是超过 10 个测试用例中的 7 个的时间限制。我无法进一步优化此代码。我怎么可能优化它，以便它可以在每个测试用例的 1 秒内运行。非常感谢 ！

我已经阅读了一些关于可以在 O(lg N) 中实现范围更新和查询的两种常见数据结构的教程：段树和二进制索引树（BIT / Fenwick Tree）。

我发现的大多数示例都是关于一些关联和交换操作，例如“范围内的整数之和”、“范围内的 XOR 整数”等。

我想知道这两个数据结构（或任何其他数据结构/算法，请提出）是否可以在O（lg N）中实现以下查询？（如果不是，那么 O(sqrt N) 怎么样）

给定一个整数数组 A，查询范围 [l,r] 中不同整数的个数

PS：假设可用整数的数量为〜10 ^ 5，所以 used[color] = true或位掩码是不可能的

例如：A = [1,2,3,2,4,3,1], query([2,5]) = 3，其中范围索引从 0 开始。

我正在尝试解决定义如下的问题：

糖果由从 1 到 1e6 的数字表示。如果一个人有 1 到 k 个糖果，则称他有 k 个糖果。

例如，如果一个人买了糖果 1、2 和 6，那么他有一套 2 颗糖果

给定 2 种类型的操作：吃 x 和买 x，其中 x 代表糖果数量。购买 x 只会将 x 的数量增加 1。吃 x 只会使 x 的数量减少 1。

对于每个操作，回答问题，我现在拥有的那套糖果的大小是多少？

我正在努力寻找最有效的方法来做到这一点。我想到的解决方案描述如下：

让 count[i] 定义大小为 1 - N 的数组，其中 N 是可能的最大糖果数。count[i] 存储我目前拥有的编号为 i 的糖果的数量。

让 Fenwick[i] 数组大小为 1 - N，其中 N 是最大可能的糖果数。这个数组用于构建一个 fenwick 树来存储我收藏中糖果的累积总和。此累积和不使用计数数组。累积总和计数 1 的数量（每个 1 表示我的收藏中存在糖果 x）。例如，如果我有一组 5 颗糖果，那么从 1 到 5 的累积总和是 5。如果有一组 10 颗糖果，那么从 1 到 10 的累积总和是 10...

对于购买操作，如果我的收藏中还没有糖果 x，则从索引 x 开始的累积总和加 1（这由 fenwick 树处理）。否则，我将只执行 count[x]++

对于eat 操作，执行count[x]--。如果 count[x] 现在为 0，则从索引 x 开始的累积总和减 1（这由 fenwick 树处理）。

现在解决了插入和删除的部分。困难的部分是如何获取当前集合中的糖果集的大小。

我尝试在 Fenwick 树中查询最大索引 i，从 1 到 i 的累积总和等于 i，同时每次以 2 的幂递增查询索引。

我采用作为有效糖果集合的最大索引 j 和作为无效糖果集合的最小索引 k。然后从 j 循环到 k，在每次迭代时查询 fenwick 树。一旦循环遇到无效集合，中断并输出答案。

在我看来，这会奏效。但是，这肯定不是一种有效的方法。有人能启发我更好的解决方案吗？提前致谢。

编辑（解决方案）：

我的插入和删除方法是正确的。只是我以不正确的方式搜索糖果的集合。在这种情况下，我们想要最大的数 x，其中 query(x) = x（query(x) 给出从 1 到 x 的累积和）。所以我们可以使用二分查找来找到x的最大有效值（query(x) = x）。为了实现这一点，我们只需要保留一个额外的变量来跟踪 x 的最后一个值，其中 query(x) 给出了一个有效的集合。

解的复杂度：O(log^2(N))

根据这篇论文，我发现使用两个 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. 任何帮助，将不胜感激。

假设我创建了一个前缀和长度为 N 的二叉索引树。主数组仅包含0s 和1s。现在我想找出哪个索引有一个前缀总和 M（这意味着正好有 M 1s）。

就像我的数组是a[]={1,0,0,1,1};

前缀和看起来像{1,1,1,2,3};

现在第 3 个索引（基于 0）的前缀总和为 2。

我怎样才能用 BIT 找到这个索引？

提前致谢。

对于使用 Fenwick 树的 q 次查询，如何在 n 大小的数组中查找每个索引 i 在 l 到 r 范围内的最后 k 项的总和，并且每个查询的 k 都不同。这是我团队的hackerearth黑客的一个问题教程，但我不明白他们是怎么做的，因为没有给出解释。可以请任何人解释它是如何完成的吗？

我想使用 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 树结构