我没有一个场景，但在这里不用的问题。 这是一个只是让我疯了。 有NxN的布尔矩阵最初的所有元素都为0，N <= 10 ^ 6和作为输入。 接下来将会有多达10 ^ 5个查询。 每个查询，可以任一列c中的所有元素设置为0或1，或者设置行r中的所有元素为0或1可以有另一种类型的查询，打印1层的在列c或行r的总数。
我不知道如何解决这个和任何帮助，将不胜感激。 显然每个查询一个为O（n）的解决方案是不可行的。
Answer 1:
采用了多项命令修改的想法是从Dukeling的后服用。
我们将需要2张地图和4个二进制索引树（BIT，又名树状数组）：1和图2位为行，图1和2个比特列。 让我们称他们为m_row ， f_row[0]并f_row[1] ; m_col ， f_col[0]和f_col[1]分别。
地图可以与阵列，或树状结构，或者散列法来实现。 2个图被用于最后修改存储到行/列。 由于可以有至多10 5的修改，你可以用这个事实来保存从简单的数组实现的空间。
BIT有2个操作：
-
adjust(value, delta_freq)其调整的频率value由delta_freq量。 -
rsq(from_value, to_value)代表范围总和的查询），其发现从所有频率的总和from_value到to_value以下。
让我们来声明全局变量： version
让我们定义numRow是在2D布尔矩阵的行数，并numCol是列在2D布尔矩阵的数量。
的位应具有至少MAX_QUERY + 1的大小，因为它是用来计数改变为行和列，其可以是多达查询的数量的数量。
初始化：
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(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
计数算法：
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
复杂性是在这两个更新和计数最坏的情况下对数。
Answer 2:
就拿版本只是意味着获得自动增加的，每次更新的值。
存储在每行和每列的最后一个版本和最近更新的价值。
存储行（版本和零计数和一的计数）的列表。 同为列。 所以这是只有2对整个电网的列表。
当行被更新，我们的版本设置为当前版本，并插入到列表中的行版本， if (oldRowValue == 0) zeroCount = oldZeroCount else zeroCount = oldZeroCount + 1 （所以它不是零的数量，而的倍的值与零更新）的数目。 同为oneCount。 同为列。
如果某行做了打印，我们可以得到该行的版本和最后一个值，我们做在列列表中该版本的二进制搜索（第一个值大于）。 然后：
if (rowValue == 1)
target = n*rowValue
- (latestColZeroCount - colZeroCount)
+ (latestColOneCount - colOneCount)
else
target = (latestColOneCount - colOneCount)
也不太清楚上面是否会奏效。
这对更新O（1），O（日志K）打印，其中k为更新的数量。
文章来源: Range update and querying in a 2D matrix
