在二維矩陣中進行範圍更新和查詢

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是更新次數。