2

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.

OmG
  • 18,337
  • 10
  • 57
  • 90
amitkarmakar
  • 1,223
  • 2
  • 13
  • 23
  • did you choose the BIT approach or is it a homework? – Nick Dandoulakis Feb 27 '10 at 20:54
  • 1
    There is a much easier solution that uses a stack. If this is homework and you are required to use a BIT, please tag it as such. – IVlad Feb 27 '10 at 20:55
  • 2
    You can do this without a BIT by iterating over the string with a counter. Add 1 for every `(`, subtract 1 for `)`, check that the counter doesn't go below zero and check if it is equal to zero at the end. (Thanks Mad) – Otto Allmendinger Feb 27 '10 at 21:01
  • True that works, and can be derived from the stack solution: when you read a `)`, remove the topmost `(` from the stack. If there is none, there's no solution. When you read a `(` push it on the stack. At the end, the stack has to be empty. This can easily be extended to work if you can have `[` and `]` as well. – IVlad Feb 27 '10 at 21:18
  • No its not a homework. I am trying solve of the problems with a Online judge. As per the problem statement, using a stack would surely make my solution run out of time. I have solved the problem using a segment tree. Can i post the link to the problem?? – amitkarmakar Feb 28 '10 at 05:05
  • I guess i can post it without asking[:p] https://www.spoj.pl/problems/BRCKTS – amitkarmakar Feb 28 '10 at 05:08
  • Well that's completely different from what your post says! Your post doesn't mention updates at all. You should edit your post and add the link to the problem statement. Also check my reply and say if there is anything in the links I gave you that you don't understand, and I'll explain it to you. Those links basically solve the problem for you. – IVlad Feb 28 '10 at 08:35
  • @IVLad I can't figure how i can extract the minimum cumulative sum from a BIT in O(logn)(which i have done using a segment tree). – amitkarmakar Apr 17 '10 at 08:01

1 Answers1

3

Here is a very good tutorial on Binary Indexed trees: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees and here is one that's more direct but less comprehensive: http://programmersdream.com/data-structure/binary-indexed-tree/

IVlad
  • 43,099
  • 13
  • 111
  • 179