Brackets matching using BIT
- by amit.codename13
edit: I was trying to solve a spoj problem. Here is the link to the problem :
http://spoj.pl/problems/BRCKTS
I can think of two possible data structures for solving the problem one using segment tree and the other using a BIT.
I have already implemented the solution using a segment tree. I have read about BIT but i can't figure out how to do a particular thing with it(which i have mentioned below)
I am trying to check if brackets are balanced in a given string containing only ('s or )'s.
I am using a BIT(Binary indexed tree) for solving the problem.
The procedure i am following is as follows:
I am taking an array of size equal to the number of characters in the string.
I am assigning -1 for ) and 1 for ( to the corresponding array elements.
Brackets are balanced in the string only if the following two conditions are true.
The cumulative sum of the whole array is zero.
Minimum cumulative sum is non negative.
i.e the minimum of cumulative sums of all the prefixes of the array is non-negative.
Checking condition 1 using a BIT is trivial.
I am facing problem in checking condition 2.
