2
编辑：我试图解决一个spoj问题。这里是问题的链接： http://spoj.pl/problems/BRCKTS使用BIT匹配的方括号
我可以想出两个可能的数据结构来解决问题一个使用分段树，另一个使用BIT。 我已经使用分段树实现了解决方案。我看过一点，但我无法弄清楚如何用它做特定的事情（这是我下面提到）
我想检查是否括号是只含有(一个给定的字符串中平衡's或)'s。 我正在使用一个位（二进制索引树）来解决问题。 我遵循的程序如下：
我正在取一个数组的大小等于字符串中的字符数。 我正在为)分配-1和(分配给相应的数组元素。
仅当满足以下两个条件时，括号才会在字符串中保持平衡。
- 整个数组的累积和为零。
- 最小累计和是非负的。 即，数组的所有前缀的累积和的最小值是非负的。
使用BIT检查条件1是微不足道的。 我在检查条件2
你选择BIT方法或者是作业？ – 2010-02-27 20:54:04
有一个更容易使用堆栈的解决方案。如果这是作业，并且您需要使用BIT，请为此标记。 – IVlad 2010-02-27 20:55:01
通过用计数器遍历字符串，可以在没有BIT的情况下执行此操作。为每个'（'减1，为'）'加1，检查计数器是否低于零，并检查结尾是否等于零。 （Thanks Mad） – 2010-02-27 21:01:30