Easy implementation of Compressed 2D Binary Indexed Tree for binary grid

Revision en2, by sdnr1, 2017-05-21 08:35:46

Suppose you want to solve a problem in which there is a

In this implementation an Order Statistics Tree(more about [](http://mirror.codeforces.com/blog/entry/11080)) is embedded at each node in a BIT. It only works if a 2D BIT has to be implemented for a binary grid of numbers(grid filled with only 1s and 0s). The update() function has been broken into 2 functions — insert() (to insert a 1 in the grid at a given point) and remove() (to remove a 1 from the grid).

PS: Suggestions are welcome. Please notify if there are any mistakes.

Tags binary indexed tree, 2d binary indexed tree, range query, range update

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English sdnr1 2017-05-21 22:59:54 138 Problems added
en6 English sdnr1 2017-05-21 09:47:43 10
en5 English sdnr1 2017-05-21 09:44:03 0 (published)
en4 English sdnr1 2017-05-21 09:43:14 8
en3 English sdnr1 2017-05-21 09:41:22 1568 Tiny change: 'f size $N x N$: 1 - I' -> 'f size $N \cross N$: 1 - I'
en2 English sdnr1 2017-05-21 08:35:46 260
en1 English sdnr1 2017-05-21 08:20:22 364 Initial revision (saved to drafts)