BRCKTS using binary indexed tree

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

BRCKTS using binary indexed tree

Post by tryit1 »

https://www.spoj.pl/problems/BRCKTS/

i'm trying to solve BRCKTS using binaryindexed tree.

i can find the cummulative sum between 0 and len in log(n) but how do i check if all the cummulative sum are greater than or equal to 0. This requires o(n) and we have almost k queries (k approx n). How can we make it fast.

i use this structure for fast updation.

Any easy problems on uva for binaryindexed tree .

Marius
New poster
Posts: 5
Joined: Thu Apr 10, 2008 5:55 pm

Re: BRCKTS using binary indexed tree

Post by Marius »

I solved it with segment trees. I think that it's very hard to solve it with binary indexed trees.

Post Reply

Return to “Algorithms”