编辑：我试图解决一个 spoj 问题。这是问题的链接： http: //spoj.pl/problems/BRCKTS
我可以想到两种可能的数据结构来解决问题，一种使用段树，另一种使用 BIT。我已经使用分段树实现了该解决方案。我读过关于 BIT 的文章，但我不知道如何用它做某件事（我在下面提到过）
我正在尝试检查括号是否在仅包含('s 或)'s 的给定字符串中保持平衡。我正在使用 BIT（二进制索引树）来解决问题。我遵循的程序如下：
我正在使用一个大小等于字符串中字符数的数组。我为相应的数组元素分配 -1)和 1 。(
仅当以下两个条件为真时，字符串中的括号才会平衡。
- 整个数组的累积和为零。
- 最小累积和为非负数。即数组的所有前缀的累积和的最小值是非负的。
使用 BIT 检查条件 1 很简单。我在检查条件 2 时遇到问题。