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

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]分别。

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

BIT 有 2 个操作：

• adjust(value, delta_freq)value，它调整按量的频率delta_freq。
• rsq(from_value, to_value)from_value，（rsq 代表范围求和查询），它查找从到包括在内的所有频率的总和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

在最坏情况下，更新和计数的复杂度都是对数。