Matrix Data Structure
Разница между en1 и en2, 290 символ(ов) изменены
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**

История

 
 
 
 
Правки
 
 
  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)