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

Question

我没有方案，但问题来了。这是一个让我发疯的人。有一个 nxn bool 矩阵，最初所有元素都是 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⁵ 修改，您可以利用这一事实来节省简单数组实现的空间。

BIT 有 2 个操作:

• adjust(value, delta_freq) , 它调整了 value 的频率通过 delta_freq金额。
• rsq(from_value, to_value) , (rsq 代表范围求和查询)它从 from_value 中找到所有频率的总和至 to_value包容性。

让我们声明全局变量:version

让我们定义numRow是二维 bool 矩阵中的行数，numCol是二维 bool 矩阵中的列数。

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

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