作业介绍

家庭作业

必做、

  • 希蒙发积分
  • 惆怅的希蒙
  • 最大子矩阵和plus

提高

  • 希蒙的防疫矩阵
  • 绿化达人希蒙

前缀和

作用:当程序需要大量计算数列中某一段数字之和的时候,可以通过前缀和算法优化查询的时间复杂度。
预处理:O(n)
查询:O(1)
原理:前缀和就是从位置1到位置i这个区间内的所有的数字之和,那么求l~r中的数字和,相当于用 1~r的数字和 减去 1~(l-1)的数字和,剩余的和即为l~r的数字和。

前缀和

for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i]; // 前缀和预处理算式
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", s[r] - s[l - 1]); // 前缀和查询区间和的计算

二维前缀和

作用:当程序需要大量计算数列中某一段数字之和的时候,可以通过前缀和算法优化查询的时间复杂度。
预处理:O(n*m)
查询:O(1)
原理:

紫色面积是指(1,1)(1, 1)左上角到(i,j1)(i, j - 1)右下角的矩形面积, 绿色面积是指(1,1)(1, 1)左上角到(i1,j)(i - 1, j )右下角的矩形面积。每一个颜色的矩形面积都代表了它所包围元素的和。

二维前缀和1

从图中我们很容易看出,整个外围蓝色矩形面积s[i][j]s[i][j] = 绿色面积[i1][j][i - 1][j] + 紫色面积s[i][j1]s[i][j - 1] - 重复加的红色的面积s[i1][j1]s[i - 1][j - 1] + 小方块的面积a[i][j]a[i][j];

二维前缀和2

因此得出二维前缀和预处理公式

$s[i][j] = s[i - 1][j] + s[i][j - 1 ] + a[i] [j] - s[i - 1][j - 1]$

现在要求求以(x1,y1)(x1,y1)为左上角和以(x2,y2)(x2,y2)为右下角的矩阵的元素的和。

紫色面积是指(1,1)(1, 1)左上角到(x11,y2)(x1 - 1, y2)右下角的矩形面积 ,黄色面积是指(1,1)(1, 1)左上角到(x2,y11)(x2, y1 - 1)右下角的矩形面积;

二维前缀和3

绿色矩形的面积 = 整个外围面积s[x2,y2]s[x2, y2] - 黄色面积s[x2,y11]s[x2, y1 - 1] - 紫色面积s[x11,y2]s[x1 - 1, y2] + 重复减去的红色面积 s[x11,y11]s[x1 - 1, y1 - 1]

二维前缀和4

因此二维前缀和的结论为:

(x1,y1)(x1, y1)为左上角,(x2,y2)(x2, y2)为右下角的子矩阵的和为: $s[x2, y2] - s[x1 - 1, y2] - s[x2, y1 - 1] + s[x1 - 1, y1 - 1]$

for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];  //二维前缀和预处理公式
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]); //二维前缀和查询区间的计算

题目

认领作业后才可以查看作业内容。
状态
正在进行…
题目
11
开始时间
2025-1-18 0:00
截止时间
2026-1-18 23:59
可延期
24 小时