问题标签 [fenwick-tree]

我知道 BIT 是如何工作的。但我想知道是否可以使用 BIT 来查找完整范围内的最小/最大值元素，或者更具体地说，在所有更新过程完成后查找最小值（或最大值）。现在，我知道使用段树可以很好地实现这一点，但是使用 BIT 可以做到这一点吗？

谢谢。

PS：我知道遍历完整BIT并计算每个索引的值的明显方法。我正在寻找一种更有效/优化的方式。

假设我正在跟踪 Fenwick 树中插槽的使用情况。例如，让我们考虑跟踪 32 个插槽，导致如下图所示的 Fenwick 树布局，其中网格中的数字表示底层数组中的索引，其中每个单元格中的值是由 Fenwick 树操作的计数该段中“已使用”项目的总和（即数组单元格 23 存储范围 [16-23] 中已使用插槽的数量）。最低级别的项目（即单元格 0、2、4、...）只能具有“1”（已用槽）或“0”（空闲槽）的值。

我正在寻找的是一种有效的算法来找到给定数量的连续空闲插槽的第一个范围。

为了说明，假设我有如下图所示的 Fenwick 树，其中总共使用了 9 个插槽（请注意，为了清楚起见，添加了浅灰色数字，实际上并未存储在树的数组单元中）。

现在我想找到例如 10 个空闲插槽的第一个连续范围，它应该找到这个范围：

我似乎找不到一种有效的方法来做到这一点，这让我有点头疼。请注意，由于所需的存储空间量对我的目的至关重要，我不希望将设计扩展为段树。

任何关于 O(log N) 类型解决方案的想法和建议都将受到欢迎。

编辑

赏金期到期后的更新时间。感谢所有评论、问题、建议和答案。他们让我重新思考问题，教会了我很多东西，并向我指出（再一次；有一天我可能会学到这一课），我应该在提问时更多地关注我想要解决的问题。

由于@Erik P是唯一对包含请求代码/伪代码的问题提供合理答案的人，因此他将获得赏金。

他还正确地指出，使用这种结构进行 O(log N) 搜索是不可能的。感谢@DanBjorge提供的证明，让我想到了最坏情况下的性能。

@EvgenyKluev的评论和回答让我意识到我应该以不同的方式提出我的问题。事实上，我已经在很大程度上按照他的建议做了（参见https://gist.github.com/anonymous/7594508 - 它显示了我在发布这个问题之前遇到的问题），并问了这个问题，希望有一个有效的方法来搜索连续范围，从而防止将此设计更改为段树（这将需要额外的 1024 字节）。然而，这样的改变似乎是明智之举。

对于任何感兴趣的人，可以在此处找到与此问题中使用的示例匹配的二进制编码的 Fenwick 树（以 64 位编码的 32 slot fenwick 树）：https ://gist.github.com/anonymous/7594245 。

我已经意识到 Fenwick 树，但是当我尝试在段上找到总和时，出现了 Segmentation Fault 11。

另外，我做对了吗？我的意思是，我完全理解 Fenwick 树的概念，我只是不知道我们必须对初始数组做什么？可能我需要作为论据传递给 Fenwik 类，然后与他一起工作吗？还是只是很多更新？先感谢您。

我正在尝试解决 Spoj 上的 D 查询问题。http://www.spoj.com/problems/DQUERY/ 我正在考虑设置和记忆结果，但这真的很慢。所以我在考虑二进制索引树可以帮助我为一个查询获取 lgN，但我想不出它的解决方案。谁能帮我。

形式上，范围最小查询问题是：

给定一个数组 A[0, N-1] ，找到任意两个给定索引之间具有最小值的元素的位置。

现在，标准解决方案是使用分段树，并在此处进行了描述。另一种用于解决范围查询的数据结构是二叉索引树（Fenwick Tree），它更容易理解和编码。

Binary-Indexed-Trees 可以解决范围最小查询问题吗？如何解决？更新和查询功能的实现将不胜感激。

问题是计算小于索引后值的值的数量。这是代码，但我不明白如何使用二叉索引树来做到这一点？

如果有人可以解释代码的工作原理，那将会很有帮助。

假设我们连续有n 个空框。我们将把m组硬币放入预先知道的一些连续的盒子中。我们将第一组硬币放入从i_1到j_1的盒子中，将第二组硬币放入从i_2到j_2的盒子中，依此类推。

在将所有硬币放入盒子后，让c_i盒子i中的硬币数量。我们希望能够快速确定索引为 i = s, s + 1, ... e - 1, e的框中有多少硬币 ，即我们要计算总和

有效率的。这可以通过使用Fenwick 树来完成。在没有任何改进的情况下，Fenwick 树需要O(n)空间来存储c_i（在表中；实际上，tree[i] != c_i，值存储得更智能）和 O(log n) 时间来计算上和。

如果我们有这样的情况

• n太大了，我们无法制作长度为n的表格（比如说 ~ 10 000 000 000）
• m足够小（比如说 ~ 500 000）

有一种方法可以以某种方式压缩框的坐标（索引），即只存储索引为i_1、i_2、 ... 、i_m的框就足够了。由于存储在tree[i]中的值取决于 i 的二进制表示，我的想法是对索引i_1、j_1、i_2、j_2、 ... 、i_m、j_m进行排序，并制作一棵长度为O(m)的树。然后向树中添加新值将是直截了当的。此外，为了计算总和，我们只需要找到不大于e的第一个索引最后一个不小于s。两者都可以通过二分搜索来完成。之后，可以很容易地计算总和。

问题发生在二维情况下。现在，我们在平面上有一个点(x,y)区域， 0 < x,y < n。该区域有m个矩形。我们知道它们的左下角和右上角的坐标，我们想计算有多少个矩形包含一个点(a,b)。最简单（也是我唯一）的想法是遵循一维情况的方式：对于角的每个坐标x_i存储角的所有坐标y_i。这个想法不是那么聪明，因为它需要O(m^2) =太多的空间。我的问题是

使用 Fenwick 树的问题的解决方案是首选，但每个解决方案都是受欢迎的！

我无法理解算法问题的解决方案

特别是，我不明白这部分代码的方式或原因

允许您计算每个点的左下象限中的点总数。

有人可以详细说明吗？

我知道如何在段树上进行范围更新，包括通过延迟传播向数组的任何给定段添加常量或添加 AP，并对任何给定段的总和进行后续查询，但不能将相同的想法应用于几何级数。

如何通过使用具有相同渐近时间复杂度的线段树来实现这一点(log(N))？

例如，如果数组是 :
a[1], a[2], .... , a[l],a[l+1]...a[r-1], a[r] ... a[n - 1], a[n] 并且如果我们用 d 的共同比率更新 [l, r] 那么更新后的数组将是 a[1], a[2], .... , a[l] + d, a[l+1] + d^2 ...a[r-1] + d^(l-r), a[r] + d^(l-r+1) ... a[n - 1], a[n]

并且仍然应该能够查询 log(n) 中任何段的总和。

我尝试用 Java 实现 Fenwick 树，但没有得到想要的结果。这是我的代码：

当我提供输入时：

10
1 2 3 4 5 6 7 8 9 10

我得到：

13
19

所以增量函数工作正常。但是 query(4) 应该给出索引 4 的累积总和，即

(1 + 2 + 13 + 4 + 5) = 25