该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

二维前缀和算法详解

一、算法概念

二维前缀和是一种用于快速计算二维数组（矩阵）中任意子矩阵元素之和的数据结构与算法。它通过预处理构建一个前缀和矩阵，将原本需要O(nm)时间复杂度的子矩阵求和操作优化为O(1)，极大提升了多组查询场景下的效率。

二、核心定义

• 原矩阵：设二维数组a[i][j]表示原始矩阵中第i行第j列的元素（本文中数组索引从1开始，便于边界处理）。
• 前缀和矩阵：定义s[i][j]为原矩阵中前i行、前j列所有元素的总和（即左上角为(1,1)，右下角为(i,j)的子矩阵之和）。

三、前缀和矩阵的构建（推导公式）

公式推导

s[i][j]的计算基于其相邻的前缀和元素，推导过程如下：

1. 要计算s[i][j]，可以先考虑其左侧区域s[i][j-1]（第i行前j-1列的和）和上方区域s[i-1][j]（前i-1行第j列的和）。
2. 但s[i][j-1]和s[i-1][j]的重叠部分s[i-1][j-1]被重复计算了，因此需要减去一次。
3. 最后再加上当前元素a[i][j]，得到完整的前i行前j列总和。

公式：
s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + a[i][j]

边界处理

• 当i=0或j=0时（即第0行或第0列），前缀和s[0][j]和s[i][0]均为0（无元素可求和）。
• 这种设定简化了边界计算，无需额外判断i=1或j=1的特殊情况。

四、子矩阵和的查询（应用公式）

问题描述

已知子矩阵的左上角坐标为(x, y)，右下角坐标为(xx, yy)，求该子矩阵内所有元素的和。

公式推导

1. 以s[xx][yy]为基础（包含从(1,1)到(xx,yy)的所有元素）。
2. 减去左侧多余区域：s[xx][y-1]（从(1,1)到(xx,y-1)的区域）。
3. 减去上方多余区域：s[x-1][yy]（从(1,1)到(x-1,yy)的区域）。
4. 由于步骤2和步骤3中重复减去了s[x-1][y-1]，因此需要加回一次。

公式：
子矩阵和 = s[xx][yy] - s[xx][y-1] - s[x-1][yy] + s[x-1][y-1]

五、代码解析

以下是基于C++实现的二维前缀和代码，包含前缀和矩阵的构建过程：

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

// 二维前缀和核心：快速计算子矩阵总和
// s[i][j] 表示 a数组前i行、前j列的全部元素总和
// 构建公式：s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + a[i][j]
// 查询公式：子矩阵(x,y)-(xx,yy)的和 = s[xx][yy] - s[xx][y-1] - s[x-1][yy] + s[x-1][y-1]

int n, m;          // 矩阵的行数和列数
int a[110][110];   // 原始矩阵
int s[110][110];   // 前缀和矩阵

int main() {
    cin >> n >> m;  // 输入矩阵大小
    
    // 读入原始矩阵并同步计算前缀和矩阵
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> a[i][j];  // 输入原始元素
            // 应用构建公式计算s[i][j]
            s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + a[i][j];
        }
    }
    
    // 此处可添加查询逻辑，例如：
    // int x, y, xx, yy;
    // cin >> x >> y >> xx >> yy;
    // int sum = s[xx][yy] - s[xx][y-1] - s[x-1][yy] + s[x-1][y-1];
    // cout << sum << endl;
    
    return 0;
}

六、示例说明

假设原始矩阵为：

1 2 3
4 5 6
7 8 9

构建前缀和矩阵s：

• s[1][1] = 1
• s[1][2] = s[1][1] + s[0][2] - s[0][1] + a[1][2] = 1 + 0 - 0 + 2 = 3
• s[1][3] = 3 + 0 - 0 + 3 = 6
• s[2][1] = s[2][0] + s[1][1] - s[1][0] + a[2][1] = 0 + 1 - 0 + 4 = 5
• 以此类推，最终s矩阵为：

  0  0  0  0
  0  1  3  6
  0  5  12 21
  0  12 27 45
  

查询示例：

求左上角(2,2)、右下角(3,3)的子矩阵和（即元素5、6、8、9的和）：

• 根据公式：s[3][3] - s[3][1] - s[1][3] + s[1][1] = 45 - 12 - 6 + 1 = 28
• 验证：5+6+8+9=28，结果正确。

七、时间与空间复杂度

• 预处理（构建前缀和矩阵）：O(nm)，需遍历整个矩阵一次。
• 单次查询：O(1)，直接通过公式计算。
• 空间复杂度：O(nm)，需存储前缀和矩阵。