问题标签 [fenwick-tree]

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

给定一个数组 A(say A[1..n]={1,2,3}) 现在我想要两个查询：

1) Update(idx,val) : 更新 A[idx]=val 的值

2）int查询（MOD）.....

我认为带有索引的 Fenwick 树作为 MOD 的所有可能值，但问题是我没有不断更新，因为每个 A[i] 的 A[i]%MOD 可能不同？我如何有效地做到这一点？

您有 n 长度数组，最初所有元素都为 0。您必须执行 2 种类型的 m 命令。

类型 1：lr (l ≤ l ≤ r ≤ n) — 将数组的所有元素加一，其索引属于范围 [l, r]。

类型 2：lr (1 ≤ l ≤ r ≤ m) — 执行索引在 [l, r] 范围内的所有命令。保证 r 严格小于
当前命令的枚举/数量。

输入：

第一行包含整数 n 和 m。接下来的 m 行包含以下格式的命令，如语句中所述：t、l、r，其中 t - 类型数（1 或 2）。

输出：

在执行每个命令后打印一个数组 a。数字必须用空格分隔。由于数字可能很大，因此以 109 + 7 为模打印。

约束：

我有一个关于已经问过这个问题的问题： SPOJ DQUERY : TLE Even With BIT?

如果我不想在进行范围查询时不考虑重复的元素怎么办？下面是一个例子：

在@kraskevich 的回答中应该做哪些必要的更改（这是针对该特定情况的有效解决方案）？我尝试add 0在 BIT 中，而不是-1在上述解决方案中，这对所有类型的查询都没有帮助。任何人都可以给我一个想法吗？

我的问题涉及二进制索引树（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的相关问题，请不要在仔细阅读之前将它们与我的合并。据我所知，这个特定的问题尚未得到解答。

我在一次在线编码竞赛中看到了这个编码问题，但我找不到最佳解决方案。这是一个问题：
“给定一个包含 N 个整数和 Q 个查询的数组 A。每个查询具有以下类型：
1 pos val：将索引 pos 处的元素更新为 val
2 pos：找到 i 小于或的最小索引等于 pos 使得 i 和 pos 之间的所有元素都相同。”

我以某种方式相信我们可以使用段树，但我无法弄清楚段树的每个索引将代表什么。

我需要以尽可能低的时间复杂度在所有子数组中找到一些反转计数。
两个元素a[i]并且a[j]形成一个反演 ifa[i] > a[j]和i < j

我已经尝试使用 Fenwick Tree 实现，但超出了时间限制。

我想要一个优化版本的代码：

超过时间限制

我发现很难在数组中找到反转对。我得到了数组中反转对的数量，但逻辑似乎很复杂，以至于我无法列出对。我是 C++ 新手，感谢任何帮助。

期待这个输出

给定数组有六个反转（8,4）和索引（0,1），（4,2）和索引（1,2），（8,2）和索引（0,2），（8,1）和索引（0,3）、（4,1）和索引（1,3）、（2,1）和索引（2,4）

该程序创建了新的数组 BITree[]，使其更加复杂。如何找到元素的位置。

链接到代码 Pastebin

样本输入：
5 6
3 1 4 1 5
1 2 4 8 16
2 5 2
1 3 5
2 3 4
2 1 4
2 5 1
2 3 3

示例输出：
22
13
-1
22
5

我正在尝试这个问题，我已经实现了一个 Fenwick 树来计算树路径上节点值的总和。Fenwick 树已在 DFS 数组上实现，该数组将节点值在“输入”时间存储为正，在“输出”时间存储为负[（链接到引用的算法）]（https://codeforces.com/blog/entry /78564）。

如果 h[i] > h[j]（高度），则从节点 i 到节点 j 有一条边，并且不能有改变方向的边，即必须以增加或减少 i 的方式添加边。每个节点的值存储在向量 a 中并且可以更新。所以我从两个方向构建了 2 棵树。

样本输入和样本边缘的图像

该程序对于示例测试用例运行良好。但它甚至在约束 N, Q <= 1000 上也给出了 TLE。问题的原始约束是 N, Q <= 2*10 ⁵

Pl 向量存储从左到右根的树的父级。Pr 存储从右到左的树的父级。同样，我创建了arrayl 和arrayr（DFS 数组）、timer 和timel（开始和结束时间数组）。

查询有两种类型：
询问是否存在路径，然后找到最大节点和。
或者更新某个节点的值。

我计算出程序的顺序大约为O((N+Q)logN)。我错了吗？我在代码中哪里出错了？

参考：
需要动态编程的爬山问题
https://www.geeksforgeeks.org/next-greater-element/
https://medium.com/@adityakumar_98609/fenwick-tree-binary-index-tree-aca7824d9c2a

在进一步澄清的情况下添加评论。我已经发布了尽可能多的相关信息。

我试图使用 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 个元素但不确定。请让我知道我应该对我的代码进行哪些更改，以及有关将来如何处理此类情况的任何其他建议。

先感谢您 ：）