算法导论4-5,算法导论4.4-3
Yyds干货库存
写在前面：本系列文章旨在复习算法刷题常用的基本算法和数据结构，用详细的图例进行讲解，总结相应的代码模板，结合实例，达到最佳的学习效果。本专栏面向零基础算法，但有一定C基础知识的学习者。如果C基础不扎实，请参考：10分钟快速复习C语法，进行语法复习。
本文已收录于算法基础系列专栏：算法基础课程免费订阅，持续更新。
和前缀一维前缀和原数组a[i]: a[1]，a[2]，a[3].a[n]；
并且：S[i]=a[1] a[2] a[3].a[n]
1:模板：如何找到S_i[n]？
2.模板：查找[l，r]
[l，r]=S _ r-S _(l-1)
从下标1开始，为了定义S_{0}=0，这个定义的好处是[l，r]=S_r-S_{l-1}，这个公式可以适用于所有场景，包括[1，x]=S[x]-S[0]。
示例：前缀并输入长度为n的整数序列。
接下来，输入m个查询，每个查询有一对L，r。
对于每个查询，输出原始序列中从第1个数字到第R个数字的总和。
输入格式
第一行包含两个整数n和m。
第二行包含n个整数，表示一个整数序列。
接下来的m行，每一行包含两个整数L和R，表示查询的区间范围。
输出格式
总共m行，每行输出一个查询结果。
数据范围
1 l r n，1 n，m 1000001000 序列中元素的值1000。
输入样本：
5 3
2 1 3 6 4
1 2
1 3
2 4
输出样本：
三
六
10
代码# include bits/stdc . h
使用命名空间std
const int N=100010
int a[N]，s[N]；
int main()
{
IOs:sync _ with _ stdio(false)；
int m，n；
scanf(%d%d ，n，m)；
for(int I=1；I=n；i )scanf(%d ，a[I])；
for(int I=1；I=n；I)s[I]=s[I-1]a[I]；
while( m -)
{
int l，r；
scanf(%d%d ，l，r)；
printf(%d\n ，s[r]-s[l-1])；
}
返回0；
}二维前缀和S[i][j]:两个方向的前缀和，左上角所有元素的和。
A[i][j]:元素。
首先，写出计算前缀总和的公式：
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]
请注意，这里最好将每个网格视为一个元素。
示例：子矩阵之和输入一个N行M列的整数矩阵，然后输入Q个查询。每个查询包含四个整数x1、y1、x2、y2，代表子矩阵的左上角坐标和右下角坐标。
对于每个查询，输出子矩阵中所有数字的总和。
输入格式
第一行包含三个整数N，M和q。
接下来的n行，每一行包含m个整数，代表一个整数矩阵。
下一个Q行，每一行包含四个整数x1、y1、x2、y2，表示一组查询。
输出格式
总共q行，每行输出一个查询结果。
数据范围
1 n，m10001q200001x1x2n1y1y2m 1000矩阵中元素的值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
代码#包含iostream
使用命名空间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；我)
for(int j=1；j=m；j)
scanf(%d ，a[I][j])；
for(int I=1；I=n；我)
for(int j=1；j=m；j)
//找到前缀sum
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)；
//计算部分前缀和
printf(%d\n ，s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]s[x1-1][y1-1])；
}
返回0；
}
，谢绝转载，否则将追究法律责任。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。