algorithm - 二维矩阵中的范围更新和查询

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，又名 Fenwick 树）：1 个映射和 2 个用于行的 BIT，1 个映射和 2 个用于列的 BIT。让我们称它们m_row为 ,f_row[0]和f_row[1]; m_col,f_col[0]和f_col[1]分别。

Map 可以用数组、树状结构或散列来实现。2 个映射用于存储对行/列的最后修改。由于最多可以有 10 ^{5 个}修改，因此您可以使用该事实来节省简单数组实现的空间。

BIT 有 2 个操作：

• adjust(value, delta_freq)，它调整了value按delta_freq数量的频率。
• rsq(from_value, to_value), （rsq 代表范围和查询）它找到所有频率的总和 fromfrom_value到to_valueinclusive。

让我们声明全局变量：version

让我们定义numRow2D 布尔矩阵中的行数和 2D 布尔矩阵numCol中的列数。

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

Take version just to mean a value that gets auto-incremented for each update.

Store the last version and last update value at each row and column.

Store a list of (versions and counts of zeros and counts of ones) for the rows. The same for the columns. So that's only 2 lists for the entire grid.

When a row is updated, we set its version to the current version and insert into the list for rows the version and if (oldRowValue == 0) zeroCount = oldZeroCount else zeroCount = oldZeroCount + 1 (so it's not the number of zero's, rather the number of times a value was updated with a zero). Same for oneCount. Same for columns.

If you do a print for a row, we get the row's version and last value, we do a binary search for that version in the column list (first value greater than). Then:

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

Not too sure whether the above will work.

That's O(1) for update, O(log k) for print, where k is the number of updates.