**Edit (2): an other version of the problem is the following: We are given a set S of m pairs of integers (x(i), y(i)).↵
For every i<=m we have x(i), y(i) <= n.↵
We are also given Q queries.↵
Every query is an integer k and a sequence T of k integers, each <= n.↵
If there is a pair (x, y) in S such that x not in T and y not in T, then we answer true. Otherwise, we answer false.**↵
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**
For every i<=m we have x(i), y(i) <= n.↵
We are also given Q queries.↵
Every query is an integer k and a sequence T of k integers, each <= n.↵
If there is a pair (x, y) in S such that x not in T and y not in T, then we answer true. Otherwise, we answer false.**↵
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**
