問題

303. 範囲和検索（一次元配列）

整数配列 nums が与えられた場合、以下の種類の複数のクエリを処理する必要があります：

1. インデックス left と right （left と right を含む）の間にある nums の要素の 和 を計算します。ここで left <= right

NumArray クラスを実装します：

• NumArray(int[] nums) 配列 nums を使用してオブジェクトを初期化します
• int sumRange(int i, int j) 配列 nums のインデックス left と right の間の要素の 合計 を返します。left と right の両端を含みます（つまり nums[left] + nums[left + 1] + ... + nums[right]）

例 1：

入力：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
出力：
[null, 1, -1, -3]

説明：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

304. 二次元範囲和検索（行列）

二次元行列 matrix が与えられた場合、以下の種類の複数のリクエストを処理します：

• 左上角が (row1, col1)、右下角が (row2, col2) のサブ矩形範囲内の要素の合計を計算します。

NumMatrix クラスを実装します：

• NumMatrix(int[][] matrix) 整数行列 matrix を受け取り初期化します
• int sumRegion(int row1, int col1, int row2, int col2) 左上角 (row1, col1) と右下角 (row2, col2) で記述されるサブ行列の要素の 合計 を返します。

例 1：

入力: 
["NumMatrix","sumRegion","sumRegion","sumRegion"]
[[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
出力: 
[null, 8, 11, 12]

説明:
NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (赤い矩形の要素の合計)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (緑の矩形の要素の合計)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (青い矩形の要素の合計)

解法

① 一次元前缀和

class RangeSumQuery {
    private int[] prefixSum;
    
    public RangeSumQuery(int[] nums) {
        int n = nums.length;
        prefixSum = new int[n + 1];
        prefixSum[0] = 0;
        
        for (int i = 1; i <= n; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
        }
    }
    
    public int query(int left, int right) {
        return prefixSum[right + 1] - prefixSum[left];
    }
}

② 二次元前缀和

class MatrixSumQuery {
    private int[][] prefixMatrix;
    
    public MatrixSumQuery(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        prefixMatrix = new int[m + 1][n + 1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefixMatrix[i][j] = prefixMatrix[i - 1][j] + prefixMatrix[i][j - 1] 
                                   - prefixMatrix[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
    }
    
    public int query(int row1, int col1, int row2, int col2) {
        return prefixMatrix[row2 + 1][col2 + 1] - prefixMatrix[row1][col2 + 1]
               - prefixMatrix[row2 + 1][col1] + prefixMatrix[row1][col1];
    }
}

アルゴリズム

前缀和

前缀和は、配列内の特定の区間の要素の和を高速に計算するための一般的なアルゴリズムテクニックです。これは、大量の区間和のクエリを処理する問題を最適化するために使用されます。例えば、配列が与えられた場合、その中の特定の連続区間の和を求めるクエリに対応します。

アルゴリズムの原理： 前缀和の核心思想は、配列を前処理することによって、配列の先頭から各位置までの要素の累積和を計算し、これらの事前に計算された累積和を利用して、任意の区間の和をO(1)時間で求めることです。配列がAの場合、その前缀和配列をprefixとすると、prefix[i]は配列Aの0からiまでの要素の和を表します。

一次元前缀和

配列A = [1, 2, 3, 4, 5] の場合、その前缀和配列はprefix = [0, 1, 3, 6, 10, 15] となります。元の配列よりも1つ多い要素を持つのは、境界条件を簡単に処理するためです。

例えば、クエリ区間[0, 3]の場合、prefix[4] - prefix[0] を計算することで結果を得ることができます。これにより、境界条件を特別に考慮する必要がなくなります。

実際のコーディングでは、関連する配列や行列の図を紙に描いて、アルゴリズムを検証することが推奨されます。

二次元前缀和

二次元の前缀和はより複雑です。

A = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]

prefix = [ [0, 0, 0, 0], [0, 1, 3, 6], [0, 5, 12, 21], [0, 12, 27, 45] ]

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

この関係を理解するために、図を描くと助かります。

クエリの計算式は、右下角の位置に左上角-1の位置を加え、右上角と左下角を引くという考え方に似ています：

area = prefix[row2+1][col2+1] - prefix[row1][col2+1] - prefix[row2+1][col1] + prefix[row1][col1]

（コーディングの便宜上、実際の行列は元の行列より1つ大きく作られています。そのため、すべてのインデックスは元の行列に1を加えたものになっています。）