SPOJ BRCKTS Using segment tree (help!)

[Moshiur Rahman]

I was working on
https://www.spoj.pl/problems/BRCKTS/

My half solution :

Replace all the '(' with 1 and ')' with -1 and construct a new array A[ ]. ( A[i] = 1 or -1 )

calculate C[ ]. ( C[i] is the sum of the values A[0]...A[i] )

Now, for determining whether the word is correct or not you need to check if A[ ] sums up to zero and if any of the C[i]'s are negative.

The first check can be done easily.

To do the second check, build a segment tree from C[ ], where each node is a pair<int,int>. Here, pair.first is the index of the minimum in the corresponding range and pair.second is the total value added in that range without considering the parents. For the replacement operations add 2 [ for ')' to '(' ] or -2 [ for '(' to ')' ] with all the values in C[i...n]. The replacement is performed in the i-th position. This can be done in log(n) with the segment tree.

But, how can I find the minimum in C[ ], in less than O(n), using this segment tree? Do I need to add any extra information or perform any special operation?

I am new to the concept of segment trees.

Thanks in advance and sorry for the long description.