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