Need Help in 2D Segment Tree Implementation

Правка en1, от 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 ?

Теги #data structure, #segment tree, #matrix

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский MarkZuckerberg 2020-06-26 16:41:56 0 (published)
en1 Английский MarkZuckerberg 2020-06-26 16:41:36 864 Initial revision (saved to drafts)