attempt's blog

Range tree
By attempt, 11 years ago, In English

Hi all, I just see some solutions of round #200 div 1 D . Seem that all solutions use "range query" data struct. Some use Segment tree like con_nha_ngheo's solution . But some others use like KADR's solution. This tree i saw in codeforces and topcoder . I don't know what it is and how it work. Could anyone help me explain it or show me some notes about it?

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

If you actually tried to see if someone else asked the same question, you'd find this blog on the top of "Recent actions". It's pretty much the same thing, and there are some explanations in the comments.

As to implementation: you should try to make your own. Everyone has a different coding style, and it's best to understand what every part of your code does, for when you need to modify it for more advanced problems.

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

I'm using non-recursive segment tree in my solution, which is faster than recursive one. It doesn't support range updates and range queries at the same time, though.

→ Reply