问题标签 [binary-indexed-tree]

编辑：我试图解决一个 spoj 问题。这是问题的链接： http: //spoj.pl/problems/BRCKTS

我可以想到两种可能的数据结构来解决问题，一种使用段树，另一种使用 BIT。我已经使用分段树实现了该解决方案。我读过关于 BIT 的文章，但我不知道如何用它做某件事（我在下面提到过）

我正在尝试检查括号是否在仅包含('s 或)'s 的给定字符串中保持平衡。我正在使用 BIT（二进制索引树）来解决问题。我遵循的程序如下：

我正在使用一个大小等于字符串中字符数的数组。我为相应的数组元素分配 -1)和 1 。(

仅当以下两个条件为真时，字符串中的括号才会平衡。

• 整个数组的累积和为零。
• 最小累积和为非负数。即数组的所有前缀的累积和的最小值是非负的。

使用 BIT 检查条件 1 很简单。我在检查条件 2 时遇到问题。

如何使用二进制索引树（BIT）找到一定长度的递增子序列的总数？

实际上这是Spoj Online Judge的问题

示例
假设我有一个数组1,2,2,10

长度为 3 的递增子序列是1,2,4和1,3,4

所以，答案是2。

如何使用二进制索引树进行范围更新，以便范围内的每个元素A[k]都[i..j]更新到A[k]*c某个c常量的位置。

而且我需要在这样的更新操作之后进行点查询。

我尝试使用下面的函数，但它不起作用，这里n是数组的大小，c是我想与范围的每个元素相乘的常数。

这些是我更新范围的调用：

任何形式的帮助将不胜感激。:)

这就是问题所在，这里有一个解决方案。

第一部分很简单。这是我没有得到的第二部分，无论我多么努力。你基本上有两组区间，需要找到一个区间不完全在另一个区间内的所有交叉点。

我一直盯着问题设置器代码，直到我的眼睛开始流血。仍然无法理解这一点：

它是如何工作的？算法是什么？

社论中指出，您可以使用区间树或“二进制索引树”来解决此问题。我或多或少地了解什么是区间树以及它如何有用。但是问题设置者显然没有使用它，并且“二进制索引树”没有出现在搜索中，而是有“二进制索引树”，它处理部分总和，我看不出它是如何相关的（它可能非常好吧，它是相关的，但我不明白如何）。

有什么帮助吗？指向我需要阅读的文学作品？

我们有一个数组 arr[0 。. . n-1]。我们应该能够有效地找到从索引 qs（查询开始）到 qe（查询结束）的最小值，其中 0 <= qs <= qe <= n-1

我知道这个的数据structure Segment树。我想知道是否Binary Index Tree (BIT)也可以用于此操作。

如果是，请我如何BIT在这种情况下使用并且数组是否为静态，我们可以更改元素并更新我们的 BIT 或段树。

这个问题听起来很模糊，需要一些解释：

几周前我了解了二叉索引树。这种数据结构是一个绝妙的设计。多亏了这个视频，我实际上花了很长时间才弄清楚它是如何构建的（我的意思是……这是我第一次看不懂书面文档，不得不看有人一步一步地画一个 BIT..）

无论如何，所以（我想）我知道如何构建一个 BIT 以及结构设计背后的基本思想。现在，我很高兴能实践一些可以用 BIT 轻松解决的问题。事实上，有人已经聚集了这篇 Quora 帖子中的好问题列表。我还在 HackerRank 上尝试了一些。

我花了很长时间尝试，只解决了两个（一个自己解决，另一个从别人的解决方案中获取）..例如，这个直接连接问题..

我意识到问题永远不在于如何构建 BIT。真正的挑战是概念化问题并使用 BIT 来解决它……这真的超出了我的想象……有没有我可以用来解决这些问题的技术？

有趣的观察是.. 对于每个问题集，下面的讨论都包含一些评论，例如：

“少量... ：）”

就像任何设法解决问题的人总是以自豪的笑脸告终，没有进一步的解释:(

另外，有没有一些经典的问题是BIT解决的？

编辑

对于那些投票结束这个问题的人：请给出一个正当的理由。我相信这个问题值得在这里讨论！

当我们进行范围更新时，有人可以帮助我理解二叉索引树吗？为什么不更新每个元素，为什么只更新开始元素和结束元素

例如 0

我们必须将 BIT 中的数组元素范围更新为 arr[x] 到 arr[y] 。根据二叉索引树点更新函数。它将更新索引 x 的累积频率，并且所有那些索引 > 比 x 都会受到更新的影响.

但是，如果我们使用点更新功能进行范围更新。那为什么我们不使用点更新功能更新每个大于 x 和小于 y 的索引。由于范围更新意味着每个元素都应该使用值进行更新，并且更新起始索引和一个高于结束索引如何涵盖所有更新

为什么我们不做

.....................................................

我

我正在解决一个问题。

我的解决方案如下：

1.将[0,i]中的所有总和作为sum[i]

2.将sum向量排序为克隆向量，并根据其在克隆向量中的索引重新索引sum中的元素。将 sum 元素值作为映射反映的键，将新索引作为反映的值。将向量和元素从后到前添加到二叉索引树中，同时在clone中找到满足上下限条件的有效元素索引范围[idx1,idx2]。

3.在我们的BIT中得到从节点0到节点idx1的总和以及从节点0到节点idx2的总和。如果节点已经插入到 BIT 中，我们将在 BIT 中找到该节点。所以满足我们绑定条件的节点数量就是总和。

错误：输入：[-2,5,-1] -2 2 输出：197 预期：3

而且我真的不知道如何格式化我的代码，我总是这样写 c++..

对不起，它有点长，我想了几天仍然不知道哪里出了问题。任何想法表示赞赏！

这是从索引 0 到索引 X 的求和查询的代码

我有两个数组BIT[] and a[]。我将数组 a 中的值存储到 BIT 以进行查询。现在根据循环，我们所做的是在索引 X 处添加值，然后通过从中删除最后设置的位来更改索引。

例如，如果我调用 query(14) 它将执行如下：

总和= BIT[14] + BIT[12]+ BIT[8]

它将在索引 8 之后停止，因为 8 是1000，并且在删除最后一位之后它变为 0 并且循环结束。所以这意味着对于索引 14 即1110我访问数组 3 次，即是设置位的数量。但是我检查了长位，它失败了，例如1000110111011101100设置位是 11 但答案是 12 。那么有没有其他方法可以通过查看索引 I 的二进制值来判断在 sum 查询执行期间访问数组的次数？

我想不通。我尝试了很多情况，对于某些情况，它小于 1，对于某些情况，它大于 1，而对于某些情况，它实际上是答案。

请帮帮我。

我正在尝试解决以下问题：

给定一个具有整数权重（任意顺序）的项目数组，我们可以有 2 种可能的操作：

查询：输出权重为 k 的项目数，范围为 x 到 y。
更新：将某项索引处的权重更改为 v。

例子：

给定数组：[1,2,3,2,5,6,7,3]

如果我们从索引 1 到 3 中查询权重为 2 的项目数，那么答案将是 2。

如果我们将索引 2 处的元素修改为权重为 2，那么我们再次进行相同的查询，答案将是 3。

这当然是一个段树问题（使用点更新）。但是，我在这里遇到了一个问题——每个段只能保存 1 个索引的答案。因此，似乎我必须在我的段树中使用向量。但这会使事情变得过于复杂。此外，我也不知道该怎么做。

有人能建议我更好的解决方案吗？