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
Why do you think a lazy 2d- segment tree does not exist?
Either way, your updates are quite simpler than a general case. Let's keep an array numElements[2][N] which tells you how many nonzero elements are in row/column i, and numOnes which tells you the number of ones in the matrix. We can initialize these variables in O(|matrix|).
For the update, if numElements[0][x] > 0 or numElements[1][x] > 0, then just go through every position in row x or column x and shift them to 0, updating our variables in the process. In total you will only iterate N times, and each iteration you go through N elements, for a total of O(N^2). You can see this by the fact that you only try to clear each element once in the process.
EDIT: I understand from your edits that amortized constant is not enough, and you want general sublinear. You see to be again insisting that lazy 2d segment trees are not possible. See https://www.quora.com/Is-it-possible-to-make-a-Segment-Tree-on-2D-with-Lazy-Propagation
Auto comment: topic has been updated by LeBronJamez (previous revision, new revision, compare).
Auto comment: topic has been updated by LeBronJamez (previous revision, new revision, compare).