Matrix Data Structure

Revision en2, by LeBronJamez, 2017-07-18 23:40:46

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 (**Edit: I should have stated this in a better way; what i meant was that there is no efficient algorithm/data structure (i.e. with sublinear complexity) for ranged updates/queries in 2D**). 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 :) Edit: my goal is to achieve sub-linear complexity for both the update and the query operations

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)