Programmer - Brackets matching using BIT

Programmer Question

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.

Find the answer here