Блог пользователя sparshgunner12

Segment Trees
Автор sparshgunner12, 11 лет назад, По-английски

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?

  • Проголосовать: нравится
  • -21
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

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

→ Ответить