【算法基础课模板笔记+注释】基础算法08 ---前缀和

106 阅读 0 评论 70 点赞

我是靠谱客的博主疯狂超短裙，这篇文章主要介绍【算法基础课模板笔记+注释】基础算法08 ---前缀和，现在分享给大家，希望可以做个参考。

声明

本文资料参考acwing算法基础课
地址：https://www.acwing.com

数组

概述

解决问题：求一个数组中部分连续数的和
初始化时间复杂度为O(n)，求解时间复杂度为O(1)

模板记忆

这个模板分为两个部分：

输入：s[i] = s[i - 1] + a[i]
输出：s[r] - s[l - 1]

注意的点：s和a都从1开始

模板代码

复制代码

1
2
3
4
5
6
// 输入
for (int i = 1; i <= n ;i ++ ) s[i] = s[i - 1] + a[i];
// 输出
printf("%dn",s[r] - s[l - 1]);

矩阵

概述

解决问题：求一个矩阵中一块数的和
初始化时间复杂度为O(n*n)，求解时间复杂度为O(1)

模板记忆

这个模板分为两个部分：

输入：s [ i ] [ j ] = s[ i - 1 ] [ j ] + s[ i ][ j - 1 ] - s[ i - 1 ][ j - 1 ] + a[ i ][ j ]
输出：s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]

注意的点：s和a都从1开始

模板代码

复制代码

1
2
3
4
5
6
7
8
// 输入
for (int i = 1; i <= n; i ++ )
    for (int j = 1; j <= m; j ++ )
        s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
// 输出
printf("%dn", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);