题意

给出n行m列的矩阵，每次查询求左上角为 (x1,y1) 、右下角为 (x2,y2) 的子矩阵的元素之和

思路

二维前缀和维护

Go代码

package main

import (
    "fmt"
)

func main() {
    var n,m,q,x1,y1,x2,y2 int 
    fmt.Scan(&n,&m,&q)
    a := make([][]int,n+1)
    sum := make([][]int,n+1)
    for i := 0 ; i <= n ; i ++ {
        sum[i] = make([]int, m+1)
    }
    for i := 1; i <= n; i ++ {
        a[i] = make([]int, m+1)
        for j := 1; j <= m; j ++ {
            fmt.Scan(&a[i][j])
            sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + a[i][j];
        }
    }
    for ; q> 0; q -- {
        fmt.Scan(&x1,&y1,&x2,&y2)
        fmt.Println(sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1])
    }
}