标签: fenwick-tree

例如:

int get(int i) {
    int res = 0;
    while (i) {
        res = (res + tree[i]) % MOD;
        i -= ( (i) & (-i) );
    }
    return res;
}

树更新功能:

void update(int i, int val) {
    while (i <= m) {
        tree[i] = (tree[i] + val) % MOD;
        i += ( (i) & (-i) );
    }
}

你能用它解释一下他们在代码中做了什么( (i) & (-i) )吗？

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

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

两个操作都是在O(log(n))其中n是一个数组的大小.理解如何进行操作及其背后的逻辑,我没有任何问题.

我的问题是如何从数组初始化Fenwick树.很明显,我可以O(nlog(n))通过调用n时间来实现这一点update(i, arr[i]),但有没有办法将其初始化O(n).

如果维基百科告诉您可以初始化,我为什么要问这个nlog(n)？因为这篇文章是如此简陋,我不确定它是否是人们能够实现的最佳复杂性.还可以通过逐个填充堆来完成与初始堆创建的相似之处,并且可以在O(nlog(n))智能堆初始化中实现O(n),这使我希望在Fenwick树中可以完成类似的操作.

我想知道Fenwick树(或二进制索引树)是否可以修改为:

1)将一定范围内的所有元素的频率增加一定量

2)查询单个元素的频率.

这与传统的Fenwick树相反,传统的Fenwick Tree在单个元素上进行更新,并且在一个范围内完成查询(类似于反Fenwick树).

我已经阅读了一些关于两个常见数据结构的教程,这些数据结构可以在O(lg N)中实现范围更新和查询:段树和二进制索引树(BIT/Fenwick树).

我发现的大多数例子都是关于一些关联和交换操作,如"范围内的整数和","范围内的XOR整数"等.

我想知道这两个数据结构(或任何其他数据结构/算法,请提出)是否可以在O(lg N)中实现以下查询？(如果没有,O(sqrt N)怎么样)

给定一个整数A的数组,查询范围[l,r]中的不同整数的数量

PS:假设可用整数的数量是~10 ^ 5,那么 used[color] = true或者位掩码是不可能的

例如:A = [1,2,3,2,4,3,1],查询([2,5])= 3,其中范围索引是从0开始的.

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

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

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

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

我已经完成了Range更新的几个教程 - 二进制索引树的范围查询.我无法理解他们中的任何一个.我不明白建造另一棵树的必要性.

有人可以用简单的英语向我解释一下吗？

今天我听了关于fenwick树(二进制索引树)的讲座,老师说这个树是区间树和分段树的概括,但我对这三个数据结构的实现是不同的.这个假设是真的吗？为什么？

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

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

两个操作都O(log(n))及时完成,我理解逻辑和实现.实现一堆其他操作并不难,比如找到从N到M的总和.

我想了解如何使Fenwick树适应RMQ.很明显,改变Fenwick树的前两个操作.但我没有弄清楚如何在从N到M的范围内找到最小值.

在寻找解决方案之后,大多数人认为这是不可能的,并且少数人声称它实际上可以完成(方法1,方法2).

第一种方法(用我的谷歌翻译写的俄语有0个解释,只有两个函数)依赖于三个数组(初始,左和右),因为我的测试对所有可能的测试用例都没有正常工作.

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

鉴于有争议的主张,我想知道是否有可能增加Fenwick树来回答update(index, value)和findMin(from, to).

如果有可能,我会很高兴听到它是如何运作的.

假设我正在跟踪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插槽fenwick树):https://gist.github.com/anonymous/7594245 .

正式地,范围最小查询问题是:

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

现在,标准解决方案是使用分段树,这里已经描述过了.用于解决范围查询的另一个数据结构是二进制索引树(Fenwick树),它更容易理解和编码.

可以通过二叉索引树来解决范围最小查询问题,以及如何解决？将理解更新和查询功能的实现.