Matrix Data Structure

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

Теги #data structure, boolean-matrix, #algorithms

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский LeBronJamez 2017-07-19 02:41:38 8
en4 Английский LeBronJamez 2017-07-19 02:41:15 384
en3 Английский LeBronJamez 2017-07-18 23:41:16 2
en2 Английский LeBronJamez 2017-07-18 23:40:46 290
en1 Английский LeBronJamez 2017-07-18 19:45:49 842 Initial revision (published)