问题标签 [fenwick-tree]

首先，将一串“平衡”括号定义为一个字符串，这样对于每个“（”，在该“（”之后的某处都有一个唯一的匹配的“）”。

例如，以下字符串都是“平衡的”：

()

()()

(())()

虽然这些不是：

)(

())(

给定一个括号字符串（长度 <= 1,000,000）和一个范围查询列表，找到每个 <= 100,000 个查询的每个范围内平衡括号的最大长度（对范围使用 0 索引）

前任：

()))()(())

范围：[0,3] -> 最长 = 2：“()”

范围：[0, 4] -> 最长 = 2：“()”

范围：[5, 9] -> 最长 = 4：“(())”

我的想法如下：

首先，只要确定一个字符串是否“平衡”就可以通过维护一个堆栈来完成。如果遇到'('，则压入堆栈，遇到')'，则从堆栈中弹出。如果最后有任何 '(' 仍然存在，则字符串不是“平衡的”。

但是，对所有范围重复此操作是 O(N*M) 复杂度，这对于输入的大小来说太长了。

现在，在注意到范围查询时，会想到前缀和和二叉索引树/段树。如果您可以将整个前缀和范围预先计算到一个数组中，那么您可以通过取差来找到更小的前缀和，这将具有良好的 big-o 复杂性。

我的想法是给'（'分配一个+1值，给'）'分配一个-1值，这样每次你遇到'（'你加一个到累积和当你遇到'） '你减少了。因此，对于一个有效的“平衡”字符串，))()你会得到：-1 -2 -1 -2.

但是，我的问题是您如何使用它来确定它是否“平衡”？此外，因为您需要在给定间隔内找到最大的“平衡”字符串，所以如何使用检查给定子字符串是否“平衡”的能力来找到该给定间隔内的最大字符串。

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

长度为 3 的递增子序列是 1,2,4 和 1,3,4（基于索引）。

所以，答案是 2。问题 LINK

我想要一个使用 BIT 树的更好的解决方案，它可以改进我的解决方案。我尝试过使用 BIT 树，但给了我超出时间限制的错误。

这是BIT 实现代码。

我也尝试过直接的方法

请帮我

我写了一个程序，它通过获取命令's'来给出范围的总和，并通过命令'u'更新一个元素，但它工作不正确。请帮帮我。

正确的工作：

输出：

我计算新旧值之间的增量，然后更新 fenwick 树，但它对我不起作用。

这是我要解决的问题，我正在使用The Fact That Prefix Sum[i] - Prefix Sum[i-1]导致频率大于零的线索来识别不同的数字，然后我正在消除频率，但即使使用 BIT，我也得到了 TLE

给定一个包含 n 个数字 a1、a2、...、an 和一些 d 查询的序列。

d-query 是一对 (i, j) (1 ≤ i ≤ j ≤ n)。

对于每个 d-query (i, j)，您必须返回子序列 ai、ai+1、...、aj 中不同元素的数量。

代码是：

我已经阅读了一些范围更新的教程 - 二进制索引树的范围查询。我无法理解其中任何一个。我不明白建造另一棵树的必要性。

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

给定一个数组（未排序）和几个范围查询。对于每个查询，我需要找到给定范围内的唯一数字的数量。这是我想出的天真的方法。

执行此操作的最有效方法是什么？我认为这可以使用二进制索引树来完成，但无法提出解决方案。

我计划在 Java中实现一个非固定大小的Fenwick 树。即，允许通过添加/删除元素来交叉范围查询的 Fenwick 树。

到目前为止，我看到的所有实现和示例都是针对固定大小的 Fenwick 树，其中元素的数量在预处理频率之前是已知的。它们使用固定大小的数组，因此在预处理完成后无法添加或删除元素。（嗯，这是可能的，但我需要重新构建结构）。

我想过扩展TreeMap或可能AbstractMap，但TreeMap实际上是一棵红黑树，我不知道如何在不丢失重新平衡过程中涉及的节点的累积和的情况下实现红黑机制（使树保持平衡） .

所以我想也许我应该采取另一种方法：为什么不扩展或调整一个简单的随机访问ArrayList并在调整基础数组大小时重新计算所有累积和？这当然会产生影响，但是，嘿，这正是 aHashMap所做的。

这就是为什么我想先在这里问一下，以防有人已经这样做了，并检查您认为哪种方法最好。

语境

我有一个应用程序，它从表中选择一个加权随机条目，其中前缀总和（权重）是关键部分。简化的表定义如下所示：

其中`fenwick`存储 的 Fenwick 树表示中的值`weights`。

让每个条目的“范围”跨越其前缀总和及其前缀总和 + 其权重。@r应用程序必须在 和之间生成一个随机数0，SUM(weight)并找到范围包含 的条目@r，如下所示：

Fenwick 树与MEMORY引擎和二分搜索相结合，应该允许我及时找到适当的条目O(lg^2(n))，而不是O(n)使用简单查询的时间：

研究

由于多个查询的开销，我一直在尝试将前缀和运算浓缩到一个查询中（与脚本语言中看到的多个数组访问相反）。在这个过程中，我意识到传统的求和方法，包括以降序键顺序访问元素，只会对第一个元素求和。WHERE当子句中存在变量时，我怀疑 MySQL 会线性地遍历表。这是查询：

其中@entryid是我们正在计算其前缀总和的条目的 ID。我确实创建了一个有效的查询（以及一个lft返回整数最左边位的函数）：

但这只是证实了我对线性搜索的怀疑。查询也是如此EXPLAIN：

指标：

现在，我看到很多问题都在询问如何消除变量中的变量WHERE以便优化器可以处理查询。但是，我想不出这个查询可以不用id=@n. 我已经考虑将我想要求和的条目的键值放入一个表中并使用连接，但我相信我会得到不良影响：要么是过多的表，要么是通过评估来进行线性搜索@entryid。

问题

有什么方法可以强制 MySQL 使用该查询的索引？如果他们提供此功能，我什至会尝试不同的 DBMS。

给定一个未排序的 n 个整数数组，我知道我可以按照以下方法在 O(N lg N) 中使用 BIT 找到反转的总数：Count Inversion by BIT

但是，如果我必须查询 O(lg N) 中的总反转数的任意范围，是否有可能？

AO(N lg N) 预计算是可以接受的。

我做了一些研究，似乎 N 因素是不可避免的......任何建议将不胜感激！

我已经使用函数 RangeUpdate() 实现了 Fenwick Tree (BIT)，以将每个元素更新（增量）到某个范围内某个值。除此以外，我实现的所有其他功能都可以正常工作。它不会按给定值递增每个元素。这个功能有什么问题？这是我的代码：

为什么函数RangeUpdate(int i, int j, int Value, int Size)没有将每个元素更新到范围内？