Need Help in 2D Segment Tree Implementation

Revision en1, by MarkZuckerberg, 2020-06-26 16:41:36

I recently came across a problem in which there was a binary matrix (cells with 0 or 1).

There were two types of queries

  1. Find no of '1' in rectangle formed by corners (r1,c1) and (r2,c2)

  2. Toggle the bit at (r3,c3)

If there were no queries of second type, i could have used pre-computation to solve this. But second query made me think about segment tree on matrix.

Now i found this article Cp Algorithms , It has a pretty neat implementation of 2D Segment Tree, but the code has no comments or description, some comments would have been made it easier to grasp.

Another article E-Maxx seems better but it's in russian i believe.

Can someone share some easy implementation on 2D Segment Tree ?

Tags #data structure, #segment tree, #matrix

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English MarkZuckerberg 2020-06-26 16:41:56 0 (published)
en1 English MarkZuckerberg 2020-06-26 16:41:36 864 Initial revision (saved to drafts)