问题标签 [binary-indexed-tree]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
c++ - “x += x & (-x)”是什么意思？
我发现很多人使用x += x & (-x),x -= x & (-x)来解决区间树问题（在实现数据结构如段树、二叉索引树等时）。
你能解释一下这个等式是什么意思吗？
例如：
algorithm - 我们如何计算前缀范围更新的加权累积平方和加一？
给定一个数组A的n元素都以0s 开头，另一个数组W也有 n 个元素（都大于0），我们要重复执行以下操作；
对于给定的 k，将A[0], A[1], .... A[k]每个增加 1，并报告 的值A[0]^2 * W[0] + A[1]^2 * W[1] + ... + A[n-1]^2 * W[n-1]。
寻找O(log n)解决方案（每个查询），或者更快。
kotlin - 如何增加 kotlin 中可变列表的大小限制？
我试图使用 Fenwick 树数据结构解决关于 codeforces 的多集问题（ https://codeforces.com/contest/1354/problem/D ）。我通过了示例测试用例，但提交后出现内存限制错误，测试用例如下所述。（基本上测试用例是：
1000000 1000000
1.............1 //10^6 次
-1...........-1 //10^6 次）。
我在我的 IDE 中尝试了类似的测试用例并得到了下面提到的错误。（与上面类似，我提供的测试用例是：
1000000 1
1.............1 //10^6 次
-1
)
线程“主”java.lang.IndexOutOfBoundsException 中的异常：索引 524289 超出 java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:64) 处 java.base/jdk.internal 的长度 524289 的范围。 util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:70) 在 java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:248) 在 java.base/java.util.Objects.checkIndex(Objects.java: 373) 在 java.base/java.util.ArrayList.get(ArrayList.java:426) 在 MultisetKt.main(multiset.kt:47) 在 MultisetKt.main(multiset.kt)
这是我的代码：
我相信这是因为 BITlist 无法存储 10^6 个元素但不确定。请让我知道我应该对我的代码进行哪些更改，以及有关将来如何处理此类情况的任何其他建议。
先感谢您 ：）
c++ - 芬威克树（BIT）。在 O(logN) 中找到具有给定累积频率的最小索引
假设我有一个具有非负值的 BIT(Fenwick Tree)，我想在 O(logN) 中找到给定累积频率的最小索引。
现在，我可以这样做 O(log^2(N)) 像这样。
我知道我们可以在 O(logN) 中找到任何索引或最大索引，如此处所述，因此也希望找到具有相同时间复杂度的最低索引。树的实现方式是一种常见的方式。
希望得到您的帮助：）
algorithm - 二叉索引树：为什么“i + lowBit(i)”有效？
我知道如果我们想用 index 更新 node i，我们需要递归更新 node i = i + lowBit(i)，直到新值超过二叉索引树的大小。
我的问题是：如何证明i + lowBit(i)可以覆盖我们需要更新的所有节点？是否有可能存在索引j不在i + lowBit(i)链中且满足的节点j > i && j - lowBit(j) + 1 <= i？
提前致谢。
algorithm - 查找有多少子字符串的第一个和最后一个字符在内部重复的快速方法
这是关于我创建的子字符串的问题。我想知道如何O(nlog(n))解决这个问题，因为天真的方法很容易。这是怎么回事。你有一个字符串S。S有很多子串。在某些子字符串中，第一个字符和最后一个字符不止一次出现。找出第一个和最后一个字符不止一次的子串。
该测试用例解释只有“BCDCB”和“CDC”，其中第一个和最后一个字符相同。
除了示例情况之外，可能还有另一种情况，其中“ABACAC”是第一个字符“A”出现 3 次，最后一个字符“C”出现两次的子字符串。“AAAABB”也是另一个子字符串。
“AAAAB”不满足。
我所了解到的O(nlog(n))可能会或可能不会有助于解决方案的是二叉索引树。二叉索引树可以以某种方式用来解决这个问题。还有排序和二分搜索，但首先我想特别关注二叉索引树。
我正在寻找一个O(n log(n))或更好的空间复杂度。
字符也是 UTF-16
algorithm - 数组范围查询优于范围查询
我正在使用 Fenwick 树（方法 4）解决 geeksforgeeks 问题https://www.geeksforgeeks.org/array-range-queries-range-queries/，但无法理解解决方案。为什么我们要使用该查询的 l 和 r 迭代查询类型 2。这里 L 和 R 表示查询 L 到查询 R 的查询数组。有人可以帮我解决这个问题吗？提前致谢。