2D Segtree Problems?

Revision en1, by Divide_By_0, 2016-02-22 05:28:21

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.

Tags segtree, segtrees, 2d trees, all problems

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Divide_By_0 2016-02-22 05:29:08 131
en1 English Divide_By_0 2016-02-22 05:28:21 950 Initial revision (published)