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**
**Edit: my goal is to achieve sub-linear complexity for both the update and the query operations**
