Range update and 2D matrix query

Question

I have no script, but here is the problem. This one of them is just driving me crazy. First, there is a logical nxn matrix, all of whose elements are 0, n <= 10 ^ 6, and are specified as input. Next will be up to 10 ^ 5 queries. Each query can either be specified for all elements of column c 0 or 1, or set all elements of row r to 0 or 1. There may be a different type of query by printing the total number 1 in column c or row r.

I have no idea how to solve this, and any help would be appreciated. Obviously, the solution O (n) for each request is not possible.

Answer 1

The idea of ​​using a number to order modifications is taken from the post Dukeling.

We will need 2 maps and 4 binary indexed trees (BIT, aka Fenwick Tree): 1 map and 2 BIT for rows, 1 map and 2 BIT for columns. Call them m_row , f_row[0] and f_row[1] ; m_col , f_col[0] and f_col[1] respectively.

A map can be implemented using an array or tree structure or hash. 2 cards are used to store the latest row / column modification. Since the modification can be no more than 10 ^5, you can use this fact to save space from a simple array implementation.

BIT has 2 operations:

• adjust(value, delta_freq) , which adjusts the frequency of value to delta_freq .
• rsq(from_value, to_value) , (rsq means requesting the sum of the range), which finds the sum of all frequencies from from_value to to_value inclusive.

Declare a global variable: version

We define numRow as the number of rows in a two-dimensional Boolean matrix, and numCol is the number of columns in a two-dimensional Boolean matrix.

BITs must have a size of at least MAX_QUERY + 1, as it is used to count the number of changes in rows and columns that can be equal to the number of queries.

Initialization:

 version = 1 # Map should return <0, 0> for rows or cols not yet # directly updated by query m_row = m_col = empty map f_row[0] = f_row[1] = f_col[0] = f_col[1] = empty BIT 

Update algorithm:

 update(isRow, value, idx): if (isRow): # Since setting a row/column to a new value will reset # everything done to it, we need to erase earlier # modification to it. # For example, turn on/off on a row a few times, then # query some column <prevValue, prevVersion> = m_row.get(idx) if ( prevVersion > 0 ): f_row[prevValue].adjust( prevVersion, -1 ) m_row.map( idx, <value, version> ) f_row[value].adjust( version, 1 ) else: <prevValue, prevVersion> = m_col.get(idx) if ( prevVersion > 0 ): f_col[prevValue].adjust( prevVersion, -1 ) m_col.map( idx, <value, version> ) f_col[value].adjust( version, 1 ) version = version + 1 

Counting Schedule:

 count(isRow, idx): if (isRow): # If this is row, we want to find number of reverse modifications # done by updating the columns <value, row_version> = m_row.get(idx) count = f_col[1 - value].rsq(row_version + 1, version) else: # If this is column, we want to find number of reverse modifications # done by updating the rows <value, col_version> = m_col.get(idx) count = f_row[1 - value].rsq(col_version + 1, version) if (isRow): if (value == 1): return numRow - count else: return count else: if (value == 1): return numCol - count else: return count 

The worst case logarithmic complexity for updating and counting.

Answer 2

Take the version only to indicate a value that automatically increases for each update.

Save the latest version and latest update value in each row and column.

Save the list (versions and number of zeros and number of units) for strings. Same thing for columns. So there are only 2 lists for the entire grid.

When a row is updated, we set its version to the current version and insert the version and if (oldRowValue == 0) zeroCount = oldZeroCount else zeroCount = oldZeroCount + 1 (so this is not the number of zeros, but the number of times the value was updated with null). The same goes for oneCount. Same thing for columns.

If you print for a row, we get the version of the row and the last value, we do a binary search of this version in the column list (the first value is larger). Then:

 if (rowValue == 1) target = n*rowValue - (latestColZeroCount - colZeroCount) + (latestColOneCount - colOneCount) else target = (latestColOneCount - colOneCount) 

Not too sure if this will work.

This is O (1) for updating, O (log k) for printing, where k is the number of updates.