【模板】二维前缀和

思路

拿到这题，先想一个最朴素的做法：每次查询都遍历子矩阵求和，时间复杂度 每次查询，查询多了肯定超时。

那怎么优化？如果你学过一维前缀和，应该能想到——能不能把同样的思路推广到二维？

答案是可以的。我们先来回忆一维前缀和怎么做的：s[i] = a[1] + a[2] + ... + a[i]，区间 [l, r] 的和就是 s[r] - s[l-1]。核心思想是预处理一次，查询 O(1)。

二维也一样。我们定义 s[i][j] 为从 (1,1) 到 (i,j) 这个矩形区域所有元素的和。那问题就变成两个：

第一个问题：怎么求 s[i][j]？

画个图你就能看出来，s[i][j] 可以由它上面和左边的前缀和推出来：

$$

为什么要减 s[i-1][j-1]？因为 s[i-1][j] 和 s[i][j-1] 把左上角那块区域加了两次，得减掉一次。这就是容斥原理。

第二个问题：怎么用 s 数组回答查询？

要求 (x1, y1) 到 (x2, y2) 的子矩阵和，同样用容斥：

$$

减掉上面多出的一块、左边多出的一块，但左上角被减了两次，所以要加回来。

搞清楚这两个公式，代码就很自然了。预处理 ，每次查询 。

注意一个细节：矩阵元素可能很大，多个加在一起可能溢出 int，所以前缀和数组用 long long。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<long long>> s(n + 1, vector<long long>(m + 1, 0));
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            long long x;
            cin >> x;
            s[i][j] = x + s[i-1][j] + s[i][j-1] - s[i-1][j-1];
        }
    }
    while(q--){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1] << '\n';
    }
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        StringBuilder sb = new StringBuilder();
        in.nextToken(); int n = (int) in.nval;
        in.nextToken(); int m = (int) in.nval;
        in.nextToken(); int q = (int) in.nval;
        long[][] s = new long[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                in.nextToken();
                s[i][j] = (long) in.nval + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
            }
        }
        while (q-- > 0) {
            in.nextToken(); int x1 = (int) in.nval;
            in.nextToken(); int y1 = (int) in.nval;
            in.nextToken(); int x2 = (int) in.nval;
            in.nextToken(); int y2 = (int) in.nval;
            sb.append(s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]).append('\n');
        }
        System.out.print(sb);
    }
}

import sys
input = sys.stdin.readline

def main():
    n, m, q = map(int, input().split())
    s = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        row = list(map(int, input().split()))
        for j in range(1, m + 1):
            s[i][j] = row[j-1] + s[i-1][j] + s[i][j-1] - s[i-1][j-1]
    out = []
    for _ in range(q):
        x1, y1, x2, y2 = map(int, input().split())
        out.append(str(s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]))
    sys.stdout.write('\n'.join(out) + '\n')

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    let idx = 0;
    const [n, m, q] = lines[idx++].split(' ').map(Number);
    const s = Array.from({length: n + 1}, () => new Array(m + 1).fill(0));
    for (let i = 1; i <= n; i++) {
        const row = lines[idx++].split(' ').map(Number);
        for (let j = 1; j <= m; j++) {
            s[i][j] = row[j-1] + s[i-1][j] + s[i][j-1] - s[i-1][j-1];
        }
    }
    const out = [];
    for (let k = 0; k < q; k++) {
        const [x1, y1, x2, y2] = lines[idx++].split(' ').map(Number);
        out.push(s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]);
    }
    console.log(out.join('\n'));
});

复杂度分析

  • 时间复杂度: ，预处理前缀和 ，每次查询 ，共 次。
  • 空间复杂度: ，存储前缀和数组。

小结

二维前缀和是一维前缀和的自然推广，核心就是容斥原理——建表的时候用容斥把重叠区域减掉，查询的时候也用容斥把多余部分减掉再补回来。两个公式长得很像，背后逻辑也一样，画个 2x2 的格子手推一遍就记住了。这个模板后面在差分、二维区间问题里都会反复出现，属于必须掌握的基础工具。