过题随笔 | 【模板】二维前缀和

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int q = in.nextInt();
        int[][] a = new int [n+1][m+1];
        long[][] s = new long [n+1][m+1];
        for (int i = 1;i <= n;++i) {
            for (int j = 1;j <= m;++j) {
                a[i][j] = in.nextInt();
                s[i][j] = s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
            }
        }
        for (int qp = 1;qp <= q;++qp) {
            int x1 = in.nextInt();
            int y1 = in.nextInt();
            int x2 = in.nextInt();
            int y2 = in.nextInt();
            long ans = s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];
            System.out.println(ans);
        }
    }
}

这题一开始的时候，我没有直接想到，这种类似容斥定理的标准解法（虽然好像很久之前做过），反而思考了另外一种时间与空间复杂度都较高的算法。我认为正确性是可以保证的，但是在这题中MLE了，不过我觉得挺有意思的就记录下来吧。

我一开始想的是逐行求和（逐列也可，是对称的）。s[i,j]表示第i行前j个元素的前缀和。则答案为：

又是一个连续求和，想到再加一层前缀和，令

然后再使用一个O(n^2)的枚举，将s撇数组求出。它是一个三维数组。

这个算法达到了O(n^3)的时间复杂度和空间复杂度。但还是记录下来吧，毕竟我思考过了。#牛客AI配图神器#