问题标签 [fenwick-tree]

假设我有一个具有非负值的 BIT(Fenwick Tree)，我想在 O(logN) 中找到给定累积频率的最小索引。

现在，我可以这样做 O(log^2(N)) 像这样。

我知道我们可以在 O(logN) 中找到任何索引或最大索引，如此处所述，因此也希望找到具有相同时间复杂度的最低索引。树的实现方式是一种常见的方式。

希望得到您的帮助：）

我听说我们可以在 O(logn*logn) 中使用二进制搜索和 Fenwick 树来完成它。我们也可以使用 PBDS 在 O(logn) 中完成。有人可以解释一下如何做。如果有其他方法也请告诉。

我很难理解将 LSB 添加到当前索引如何为我们提供包含给定点的下一个位置。

任何人都可以向我解释或参考一些资源吗？我看到的所有资源都只是告诉你它有效，但没有解释为什么。我知道查询是如何工作的。

谢谢。

PS我在这里看到了同样的问题，但我还是不明白，因为他们并没有真正解释。

我需要计算数组范围内的总和，所以我遇到了 Segment Tree 和 Fenwick Tree，我注意到这两个树都以相同的渐近运行时间查询和更新。我做了更多的研究，这两种数据结构似乎以相同的速度做所有事情。两者都有线性内存使用（段树使用两倍）。

除了运行时间/内存和实现中的恒定因素之外，还有什么理由让我选择一个而不是另一个？

我正在寻找一个客观的答案，比如某个操作比另一个操作更快，或者某个限制可能有另一个限制。

我看到了其他 2 个关于此的 StackOverflow 问题，但答案只是描述了这两种数据结构，而不是解释什么时候一个可能比另一个更好。

我们有n 个玩家，每个玩家有 3 个值，分别分配给A、B 和 C。

如果存在另一个具有所有 3 个值 A[j] > A[i]、B[j] > B[i] 和 C[j] > C[i] 的玩家j ，则玩家i无法获胜。我们被要求找出无法获胜的玩家数量。

我使用蛮力尝试了这个问题，这是对玩家数组的线性搜索。但它显示TLE。

对于每个玩家i，我正在遍历完整数组以查找是否存在满足上述条件的任何其他玩家j 。

代码 ：

这种方法是O(n^2)，对于我们遍历完整数组的每个玩家。因此它给出了 TLE。

示例测试用例：

禁忌：

解决这个问题的最佳方法是什么？

解决方案：

该解决方案使用线段树，从而解决了时间O(n*log(n))和空间O(n)的问题。

@Primusa在接受的答案中解释了方法。

我有一个问题，我不知道我是否可以用 Fenwick 树解决它。这是问题所在：我有一个原始数组 a = [8,4,7,0]。现在我遍历数组，在每一步我都对排序后的子数组感兴趣，它们看起来像这样：[8]、[4,8]、[4,7,8]、[0,4,7, 8]。在插入当前数字时，在迭代的每一步中，我想知道所有大于我刚刚插入的数字的总和。所以对于上面的例子，它看起来像这样：

• [8]；sum = 0 因为所有大于插入数字 (8) 的数字之和为 0
• [4,8]；sum = 8 因为所有大于插入数字 (4) 的数字之和为 8
• [4,7,8]；sum = 8 因为所有大于插入数字 (7) 的数字之和为 8
• [0,4,7,8]; sum = 19，因为所有大于插入数字 (0) 的数字之和为 19

上面的例子只是为了说明，原始数组可以大得多，因此有效地计算这些总和变得非常重要。关于如何有效解决这个问题的任何建议？

我很难解决 Leetcode 307 Range Sum Query - Mutable and Leetcode 528: Random Pick with Index 的变体，以便设计一个数据结构，以便我可以添加元素，并且每个元素都将具有权重和基于 pop 元素与重量成正比。我正在考虑添加和弹出操作的最佳复杂度为 o(log n )，其中 n 是现有数据大小。但是，我可以找到一个好的算法/数据结构来解决它。

Fenwick 树是否作为分段树完成某些工作？它们在时间复杂度、任务和实现算法方面有什么区别？

我正在使用 Fenwick 树（方法 4）解决 geeksforgeeks 问题https://www.geeksforgeeks.org/array-range-queries-range-queries/，但无法理解解决方案。为什么我们要使用该查询的 l 和 r 迭代查询类型 2。这里 L 和 R 表示查询 L 到查询 R 的查询数组。有人可以帮我解决这个问题吗？提前致谢。

我正在解决一个 CSES 问题。这是一个简单的 Fenwick 树问题，我编写了代码，它在较小的输入上完美运行，但在较大的输入上给出错误的答案。问题链接：https ://cses.fi/problemset/task/1648/ 我的问题解决方案：

这很简单。我可能做错了什么？