title: Brackets matching using BIT
body: <p>edit: I was trying to solve a spoj problem. Here is the link to the problem :
  <a href="http://spoj.pl/problems/BRCKTS" rel="nofollow noreferrer">http://spoj.pl/problems/BRCKTS</a></p>
  
  <p>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)</p>
  
  <hr>
  
  <p>I am trying to check if brackets are balanced in a given string containing only <code>(</code>'s or <code>)</code>'s.
  I am using a BIT(Binary indexed tree) for solving the problem.
  The procedure i am following is as follows:</p>
  
  <p>I am taking an array of size equal to the number of characters in the string.
  I am assigning -1 for <code>)</code> and 1 for <code>(</code> to the corresponding array elements.</p>
  
  <p>Brackets are balanced in the string only if the following two conditions are true.</p>
  
  <ul>
  <li>The cumulative sum of the whole array is zero.</li>
  <li>Minimum cumulative sum is non negative.
  i.e the minimum of cumulative sums of all the prefixes of the array is non-negative.</li>
  </ul>
  
  <p>Checking condition 1 using a BIT is trivial.
  I am facing problem in checking condition 2.</p>