今天繼續寫前綴和題目

304. Range Sum Query 2D - Immutable (medium)

題目敘述: 給一個二維矩陣，處理下列類型的多個查詢：

計算由左上角 (row1, col1) 和右下角 (row2, col2) 定義的矩形範圍內，所有矩陣元素的總和。

實現 NumMatrix 類別：

• NumMatrix(int[][] matrix)：使用給定的整數矩陣初始化該物件。
• int sumRegion(int row1, int col1, int row2, int col2)：返回由左上角 (row1, col1) 和右下角 (row2, col2) 所構成的矩形範圍內的元素總和。

要求：設計一個時間複雜度為 O(1) 的算法來處理 sumRegion 函數。

解題思路:

這一題的重點在於高中數學裡的排容原理

圖片來源: Python-LeetCode 581 第四招 前綴和 Prefix Sum

邦一教授講解此題: 計算紅色區塊的總和，我們可以用最大的那個矩形減去左邊綠色的，減去上方黑色的，再加回左上角淺藍色那一小塊(因為它被減去兩次)。

二維前綴和的構造如:

prefix[0][0] = matrix[0][0]
prefix[1][1] = matrix[0][0] + matrix[0][1] + matrix[1][0] + matrix[1][1]

一般化的公式為：

prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] 
               - prefix[i-1][j-1] + matrix[i-1][j-1]

此題用 Rust 解題:

struct NumMatrix {
    prefix: Vec<Vec<i32>>,
}

/** 
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl NumMatrix {

    fn new(matrix: Vec<Vec<i32>>) -> Self {
        let rows = matrix.len();
        if rows == 0 { return NumMatrix { prefix: vec![] }; }
        
        let cols = matrix[0].len();
        let mut prefix = vec![vec![0; cols + 1]; rows + 1];

        for i in 1..=rows {
            for j in 1..=cols {
                prefix[i][j] = matrix[i-1][j-1] 
                + prefix[i-1][j] 
                + prefix[i][j-1] 
                - prefix[i-1][j-1];
            }
        }

        NumMatrix { prefix }
    }

    
    fn sum_region(&self, row1: i32, col1: i32, row2: i32, col2: i32) -> i32 {
        let (row1, col1, row2, col2) = 
        (row1 as usize,
        col1 as usize,
        row2 as usize,
        col2 as usize);
       
        self.prefix[row2 + 1][col2 + 1] - self.prefix[row1][col2 + 1] 
        - self.prefix[row2 + 1][col1] + self.prefix[row1][col1]
    }
}