在二维矩阵范围更新和查询 [英] Range update and querying in a 2D matrix

问题描述

我没有一个方案，但在这里不用的问题。这是一个只是让我疯了。有一个n阶布尔矩阵最初所有元素都是0，N＆LT; = 10 ^ 6和作为输入。 下一步将有高达10 ^ 5的查询。每个查询，可以任一组列的所有元素c键0或1，或者设置行r的所有元素为0或1可以有另一种类型的查询，印刷在c列或行r 1的总数。

I don't have a scenario, but here goes the problem. This is one is just driving me crazy. There is a nxn boolean matrix initially all elements are 0, n <= 10^6 and given as input. Next there will be up to 10^5 queries. Each query can be either set all elements of column c to 0 or 1, or set all elements of row r to 0 or 1. There can be another type of query, printing the total number of 1's in column c or row r.

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

I have no idea how to solve this and any help would be appreciated. Obviously a O(n) solution per query is not feasible.

推荐答案

采用多项下令修改的想法是从Dukeling的帖子。

The idea of using a number to order the modifications is taken from Dukeling's post.

我们将需要2地图和4个二进制索引树（BIT，又名分域树）：1图和2位排和1个地图和2位列。让我们称他们为 m_row ， f_row [0] 和 f_row [1] ; m_col ， f_col [0] 和 f_col [1] 分别。

We will need 2 maps and 4 binary indexed tree (BIT, a.k.a. Fenwick Tree): 1 map and 2 BITs for rows, and 1 map and 2 BITs for columns. Let us call them m_row, f_row[0], and f_row[1]; m_col, f_col[0] and f_col[1] respectively.

地图可以用数组或树状结构，或散列实现。的2映射用于将上次修改存储到行/列。既然可以有至多10 ⁵ 的修改，你可以用这个事实来保存从简单的数组实现的空间。

Map may be implemented with array, or tree like structure, or hashing. The 2 maps are used to store the last modification to a row/column. Since there can be at most 10⁵ modification, you may use that fact to save space from simple array implementation.

位有2个操作：

• 调整（值，delta_freq），其中调整值的频率按 delta_freq 量。
• RSQ（from_value，to_value），（RSQ表示距离和查询），它找到所有频率的总和，从 from_value 到 to_value 的包容性。

• adjust(value, delta_freq), which adjusts the frequency of the value by delta_freq amount.
• rsq(from_value, to_value), (rsq stands for range sum query) which finds the sum of the all the frequencies from from_value to to_value inclusive.

让我们声明全局变量：版本

Let us declare global variable: version

让我们定义 numRow行是在2D布尔矩阵的行数，而 numCol 是列在2D布尔矩阵编号

Let us define numRow to be the number of rows in the 2D boolean matrix, and numCol to be the number of columns in the 2D boolean matrix.

比特应该至少有MAX_QUERY + 1的大小，因为它是用于计算变化的行和列，其可以是多达查询的数量的数量。

The BITs should have size of at least MAX_QUERY + 1, since it is used to count the number of changes to the rows and columns, which can be as many as the number of queries.

初​​始化：

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

复杂性是对数在最坏的情况下为更新和计数。

The complexity is logarithmic in worst case for both update and count.

这篇关于在二维矩阵范围更新和查询的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！