Matrix Data Structure

Revision en1, by LeBronJamez, 2017-07-18 19:45:49

I am trying to find a data structure which, given a boolean square matrix symmetric with respect to the main diagonal, can efficiently handle the following operations: update(x): set all the entries in row x and column x to 0. query(): return true if there is at least one 1 in the matrix, return false otherwise. I've been thinking of using 2d-segment tree with lazy propagation, but after a quick search I found out that there is no such thing. The only way of efficiently doing range updates and queries in 2D is with Binary Indexed Tree, but using BIT only limits us to updating/querying sums. However, in my case the updates are quite restricted, since we only update an entire row and an entire column at a time, so I was wondering if there is some other way I could approach the problem. Any help is appreciated :)

Tags #data structure, boolean-matrix, #algorithms

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English LeBronJamez 2017-07-19 02:41:38 8
en4 English LeBronJamez 2017-07-19 02:41:15 384
en3 English LeBronJamez 2017-07-18 23:41:16 2
en2 English LeBronJamez 2017-07-18 23:40:46 290
en1 English LeBronJamez 2017-07-18 19:45:49 842 Initial revision (published)