sparshgunner12's blog

Segment Trees
By sparshgunner12, 11 years ago, In English

Hey suppose given a list of values i need to update a range(add a number to all numbers in that range) and query the number of numbers in that range smaller than 0.Can u suggest an O(log k where k is the length of the range) time complex algorithm for it.I think it's a variation of segment trees but don't know how?

  • Vote: I like it
  • -21
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I suppose that it is the part of one problem on codechef september challenge. You shoudnt discuss before end of the contest.

→ Reply
»
11 years ago, # |
  Vote: I like it -13 Vote: I do not like it

It is an article from which I learned segment tree with the queries which require the updating of some range. (But in Japanese) I think you can solve the problem with it.

You can use translating system, I think...

http://d.hatena.ne.jp/kyuridenamida/20121114/1352835261

→ Reply