问题标签 [fenwick-tree]

http://ayazdzulfikar.blogspot.in/2014/12/penggunaan-fenwick-tree-bit.html?showComment=1434865697025#c5391178275473818224

例如被告知索引-i 的函数或f(i) 的值是i ^ k，对于k> = 0 并且始终停留在这个问题上。给定如下查询：

添加值数组[i]，对于所有a <= i <= b 作为v 确定总数组[i] f(i)，对于每个a <= i <= b（记得前面函数值的说明）

要做到这一点，我们需要知道 m 和 c 的值。为此，我们需要 2 个单独的 BIT。下面观察以 ab v 的形式对每个更新进行观察。要计算 m 的值，实际上与 Range Update - Point Query 相同。对于 i 的每个值，我们可以得到以下观察结果，可能是：

通过使用以下观察，很明显范围更新 - 点查询可用于任何 BIT。要计算 c 的值，我们需要观察每个 i 值的可能性，可能是：

同样，我们需要范围更新 - 点查询，但在不同的 BIT 中。Oiya，为了一点帮助，我为 k <= 3 写了 g (x) 的值是：p：

现在，示例问题 SPOJ - Horrible Queries 。这个问题与所描述的问题类似，k = 0。还要注意，有时有一个非常极端的问题，该函数不是针对一种类型的 k，但它可能是多项式的形状！例如 LA 外星人再次绑架。为了解决这个问题，解决方案是，对于每个等级，我们分别制作其 BIT 计数器 m。BIT结合清除计数器c很好。

如果出现以下情况，我们如何使用这个概念：

给定一个整数数组 A1,A2,...AN。

给定 x,y：将 1×2 加到 Ax，将 2×3 加到 Ax+1，将 3×4 加到 Ax+2，将 4×5 加到 Ax+3，依此类推，直到 Ay。

然后返回范围 [Ax,Ay] 的总和。

问题陈述：

https://www.hackerrank.com/contests/epiccode/challenges/square-array

给定一个整数数组 A1,A2,...AN，您必须在数组中执行两种类型的查询。

• 1 x y。将 1×2 加到 Ax，将 2×3 加到 Ax+1，将 3×4 加到 Ax+2，将 4×5 加到 Ax+3，依此类推，直到 Ay。

• 2 x y。求下标x到下标y的所有整数之和以109+7为模，即求(Ax+Ax+1+⋯+Ay)mod(109+7)。

您可以假设最初数组中的所有值都是 0。

输入格式：

第一行包含两个以空格分隔的整数 N 和 Q。N 表示数组的大小，Q 表示查询的数量。

接下来的 Q 行中的每一行都将包含一个 1 xy 或 2 x y 形式的查询。

约束：

1≤x≤y≤N 1≤N≤2×10^5 1≤Q≤2×10^5

输出格式 对于 2 xy 形式的每个查询，打印所需的答案。

解释：

提交的解决方案之一：

Fenwick 树是一种允许两种操作的数据结构（您可以通过更多操作来扩充它）：

• 点更新update(index, value)
• 前缀和query(index)

这两个操作都在O(log(n))wheren是数组的大小。我在理解如何进行操作及其背后的逻辑方面没有问题。

我的问题是如何从数组中初始化 Fenwick 树。O(nlog(n))显然，我可以通过调用ntimes来实现这一点update(i, arr[i])，但是有没有办法在O(n).

如果维基百科告诉你可以初始化，我为什么要问这个nlog(n)？因为这篇文章太简陋了，所以我不确定它是否是可以达到的最佳复杂性。还与天真的堆创建相似，这是通过一个一个地填充堆来完成的，并且可以在O(nlog(n))与智能堆初始化的对比中实现，O(n)这让我希望可以在 Fenwick 树中完成类似的事情。

Fenwick 树是一种数据结构，可以有效地回答主要查询：

• 将元素添加到数组的特定索引update(index, value)
• 查找从 1 到 N 的元素之和find(n)

这两项操作都O(log(n))及时完成，我理解逻辑和实现。实现一堆其他操作并不难，比如从 N 到 M 求和。

我想了解如何为 RMQ 调整 Fenwick 树。很明显，为前两个操作更改 Fenwick 树。但我无法弄清楚如何在 N 到 M 的范围内找到最小值。

在寻找解决方案后，大多数人认为这是不可能的，少数人声称它实际上可以完成（方法1 、方法 2）。

第一种方法（用俄语编写，基于我的谷歌翻译，解释为 0，只有两个函数）依赖于三个数组（初始、左和右），因为我的测试对于所有可能的测试用例都不能正常工作。

第二种方法只需要一个数组，并且基于运行的声明，O(log^2(n))并且几乎没有解释它为什么以及如何工作。我没有尝试测试它。

鉴于有争议的说法，我想知道是否可以增加 Fenwick 树来回答update(index, value)和findMin(from, to)。

如果可能的话，我很高兴听到它是如何工作的。

天真的方法是线性迭代范围并与范围中的每个数字相乘。

示例：数组：{1,2,3,4,5,6,7,8,9,10}；将索引 3 与索引 8 相乘 2。假设一个基于索引。

结果数组应为：{1,2,6,8,10,12,14,16,9,10};

我知道二进制索引树可用于“总和”部分。如何有效地将给定范围与数字相乘？

我们可以在 fenwick 树中进行更新，例如添加一个值并乘以一个值。我有以下代码用于将值 x 添加到位置 l 的元素。

同样，我想执行乘法运算。我不知道该怎么做。任何帮助都是可观的。

我可以在有条件的 BIT 中执行范围更新吗？假设我有一组负频率和正频率 A[] = {1, -3, -4, 5, 9}。而且我想用一个条件来更新数组的值：如果更新值（x）为负，则仅更新负元素，如果更新值为正，则仅更新范围内的正值。

例如，在上述数组中，如果更新查询为 2 4 -2，（左右值），则只更新第 2（-3）和第 3（-4）位置。离开第 4(5) 个位置，因为它是一个正整数。

或者我应该使用另一个数据结构来完成这个？

我用它来学习范围更新。

我有以下 Fenwick 树算法的实现。

这个程序应该能够运行N<=5000000和处理Q<=5000000。它应该能够在 9 秒内运行。但是在提交这个问题后，我得到了超过时间限制（TLE）的判决。我已经尝试了所有措施来优化这段代码，但无济于事，它仍然给了我 TLE。我怎么可能优化这段代码，使它可以在 9 秒内运行。非常感谢。

For example:

A tree update function:

Can you please explain what they do in the code by using ( (i) & (-i) )?

问题链接在这里。问题基本上是计算给定大小 N 乘 M 矩阵的所有此类子矩阵，其元素总和介于 A 和 B 之间。N,M<=250。10^-9<=A<=B<=10^9。

人们已经使用DP和BIT解决了它。我不清楚如何。

首先，我试图解决上述问题的一个更简单的版本，一维情况：给定一个长度为 N 的数组 A，计算所有子数组，其中子数组中的元素总和位于 A 和 B 之间，但仍然不能认为比 O(n^2) 更好。这是我所做的：

我想制作另一个数组来保留原始数组的前缀和，比如前缀 [N]。前缀[i] = A 1 + A[2] + A[3] + ...A[i]。设置前缀[1] = A [1]。然后对于从 2 到 N 的每个 i，问题是计算所有 j <= i 使得总和 Z = A[j] + A[j+1] + ..A[i] 位于 A 和 B 之间。这是等价的到前缀[i] - 前缀[j-1]。但它仍然是 O(n^2)，对于每个 i，j 都在 i 位置。

任何人都可以帮助我逐步推进我解决主要问题的给定方法吗？