在二维矩阵中进行范围更新和查询

Question

我没有一个场景，但这里出现问题。这是一个让我发疯的东西。最初有一个nxn布尔矩阵，所有元素都是0，n < = 10^6，并给出输入。 接下来将会有10^5个查询。每个查询都可以将列c的所有元素设置为0或1，或者将行r的所有元素设置为0或1.可以有另一种类型的查询，在列c或行r中打印1的总数。

我不知道如何解决这个问题，任何帮助将不胜感激。显然，每个查询的O（n）解决方案是不可行的。

Answer 1

使用数字命令修改的想法取自Dukeling的文章。我们需要2个地图和4个二叉索引树（BIT，a.k.a. Fenwick Tree）：1行2位，1行2位BIT。我们称它们为m_row,f_row[0]和f_row[1];分别为m_col,f_col[0]和f_col[1]。

地图可以用数组或树状结构或散列来实现。 2个地图用于存储对行/列的最后修改。由于最多可以修改10个修改，所以可以使用这个事实来节省简单数组实现的空间。

BIT有2个操作：

• adjust(value, delta_freq)，其通过delta_freq量调整value的频率。
• rsq(from_value, to_value)，（rsq代表范围总和查询），其找出从from_value到to_value（包括to_value）在内的所有频率之和。

让我们声明全局变量：version

让我们定义numRow是在2D布尔矩阵的行数和numCol是在2D布尔矩阵的列数。

BIT的大小必须至少为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

版本只是意味着每个更新都会自动递增的值。

存储每行和每列的最新版本和最新更新值。

存储行的列表（版本和计数的零和计数为1）。栏目也一样。所以这只是整个电网的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）for update，O（log k）for print，其中k是更新次数。