Common Algorithm Implementation Templates

Traverse an array by groups

for (int i = 0; i < arr.length; i += interval) {
    for (int j = i; j < i + interval && j < arr.length; j++) {
        // do something
    }
    // do something
}

Calculate the submatrix sums fast

We can use a 2D prefix sum array. Each row of the 2D prefix sum array is a 1D prefix sum array for the corresponding row in the original matrix.

After initialization which takes $O(mn)$, calculating a submatrix sum takes $O(k)$, where k is the number of rows in the submatrix.

// given matrix[m][n]
int[][] prefixSum = new int[m][n];
// init
for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        // initialize each element in prefixSum[i]
    }
}