二维前缀和

一、算法思想

相比于 一维前缀和，二维前缀和要解决的问题是快速计算一个矩阵中任意子矩阵的和。

1.1 计算方法

$S_{i,j}=S_{i-1,j}+S_{i,j-1}-S_{i-1,j-1}+a_{i,j}$

1.2 作用

$O(1)$ 时间内计算左上角坐标 $(x_1,y_1)$、右下角坐标 $(x_2,y_2)$ 的子矩阵面积：

$S=S_{x_2,y_2}-S_{x2,y_1-1}-S_{x_1-1,y_2}+S_{x_1-1,y_1-1}$

二、算法模板

Go

type PrefixSum2D struct {
    sum [][]int
}

// NewPrefixSum2D 初始化二维前缀和
func NewPrefixSum2D(q [][]int) *PrefixSum2D {
    n, m := len(q), len(q[0])
    sum := make([][]int, n+1)
    for i := range sum {
        sum[i] = make([]int, m+1)
    }
    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + q[i-1][j-1]
        }
    }
    return &PrefixSum2D{sum: sum}
}

// 查询二维前缀和
func (ps *PrefixSum2D) query(x1, y1, x2, y2 int) int {
    return ps.sum[x2][y2] - ps.sum[x2][y1-1] - ps.sum[x1-1][y2] + ps.sum[x1-1][y1-1]
}

三、代码实战

AcWing 0796

---

题目：子矩阵的和

输入一个 $n$ 行 $m$ 列的整数矩阵，再输入 $q$ 个询问，每个询问包含四个整数 $x_1,y_1,x_2,y_2$，表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

输入格式

第一行包含三个整数 $n$，$m$，$q$。

接下来 $n$ 行，每行包含 $m$ 个整数，表示整数矩阵。

接下来 $q$ 行，每行包含四个整数 $x_1,y_1,x_2,y_2$，表示一组询问。

输出格式

共 $q$ 行，每行输出一个询问的结果。

数据范围

$1 \le n,m \le 1000$

$1 \le q \le 2 \times 10^5$

$1 \le x_1 \le x_2 \le n$

$1 \le y_1 \le y_2 \le m$

$-1000 \le \text{矩阵内元素的值} \le 1000$

输入样例：

3 4 3

1 7 2 4

3 6 2 8

2 1 2 3

1 1 2 2

2 1 3 4

1 3 3 4

输出样例：

17

27

21

解答代码：

#include <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], s[N][N];

int main()
{
    scanf("%d%d%d", &n, &m, &q);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    }

    while (q--)
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        int ans = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
        printf("%d\n", ans);
    }

    return 0;
}

package main

import (
    "bufio"
    . "fmt"
    "io"
    "os"
)

type PrefixSum2D struct {
    sum [][]int
}

// NewPrefixSum2D 初始化二维前缀和
func NewPrefixSum2D(q [][]int) *PrefixSum2D {
    n, m := len(q), len(q[0])
    sum := make([][]int, n+1)
    for i := range sum {
        sum[i] = make([]int, m+1)
    }
    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + q[i-1][j-1]
        }
    }
    return &PrefixSum2D{sum: sum}
}

// 查询二维前缀和
func (ps *PrefixSum2D) query(x1, y1, x2, y2 int) int {
    return ps.sum[x2][y2] - ps.sum[x2][y1-1] - ps.sum[x1-1][y2] + ps.sum[x1-1][y1-1]
}

func run(_r io.Reader, out io.Writer) {
    in := bufio.NewReader(_r)

    var n, m, k int
    Fscan(in, &n, &m, &k)

    q := make([][]int, n)
    for i := range q {
        q[i] = make([]int, m)
    }
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            Fscan(in, &q[i][j])
        }
    }

    ps := NewPrefixSum2D(q)

    for i := 0; i < k; i++ {
        var x1, y1, x2, y2 int
        Fscan(in, &x1, &y1, &x2, &y2)
        Fprintf(out, "%d\n", ps.query(x1, y1, x2, y2))
    }
}

func main() {
    run(os.Stdin, os.Stdout)
}