Divide_By_0's blog

By Divide_By_0, history, 8 years ago, In English

I am looking for problems that have a long, error-prone, or difficult solution(preferably the "obvious" solution) without 2D segtrees. However, the problem should also have some solution with 2D segtrees that can easily copy-paste a segment tree of fenwick tree's code (2D segment trees on sums, for instance), resulting in shorter coding time should you have the code ready. The segtree solution can be complete overkill, but as long as it takes less time to code (given the tree code) than another common solution, the problem is great.

For example, Algorithmic Crush is a great example of a problem that has a simple solution without segtrees (scroll down to this problem), but a shorter solution with a 1D segtree, provided youve coded it before and only need a few tweaks. I would like similar problems, but for 2D segtrees.

Also, the problem can be hosted anywhere (CF, TopCoder, HackerRank, etc.) so long as it has an editorial or solution somewhere.

  • Vote: I like it
  • +7
  • Vote: I do not like it