算法 - 前缀和 - 2. 模板 2D 前缀和
最编程
2024-03-23 13:05:13
...
题目地址:二维前缀和
2.1 算法原理
-
首先,定义了三个整数变量 m、n 和 q,并使用 cin 输入它们的值。其中,m 表示矩阵的列数,n 表示矩阵的行数,q 表示查询的次数。
-
创建了一个二维整数向量 arr,大小为 (n+1) × (m+1),用于存储输入的矩阵。
-
使用两个嵌套的 for 循环,从1到 n 和从1到 m,依次输入矩阵的元素,并将其存储在 arr 中。
-
创建了一个二维长整型向量 dp,大小为 (n+1) × (m+1),用于存储二维前缀和。
-
使用两个嵌套的 for 循环,从1到 n 和从1到 m,计算二维前缀和。具体做法是根据动态规划的思想,将当前位置的元素与其左边、上边和左上角位置的前缀和相加,并减去左上角位置的前缀和。将计算结果存储在 dp 中。
-
在每次查询中,使用 cin 输入查询的范围,分别为起始点 (x1, y1) 和终止点 (x2, y2)。这表示需要计算从矩阵的 (x1, y1) 位置到 (x2, y2) 位置的子矩阵的和。
-
输出 dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1],即子矩阵的和。这里的计算方式是利用二维前缀和的性质,通过相减来得到子矩阵的和。
-
重复步骤 6 到步骤 7,直到完成所有的查询。
-
返回0,表示程序顺利执行结束。
2.2 代码
#include <iostream>
#include <vector>
using namespace std;
int main() {
int m,n,q;
cin>>n>>m>>q;
vector<vector<int>> arr(n+1,vector<int>(m+1));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>arr[i][j];
}
}
//预处理dp
vector<vector<long long>> dp(n+1,vector<long long>(m+1));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
dp[i][j]=dp[i][j-1]+dp[i-1][j]+arr[i][j]-dp[i-1][j-1];
}
}
//使用
int x1=0,y1=0,x2=0,y2=0;
while(q--)
{
cin>>x1>>y1>>x2>>y2;
cout<<dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]<<endl;
}
return 0;
}
推荐阅读
-
算法 - 前缀和 - 2. 模板 2D 前缀和
-
算法练习:前缀和
-
前缀和的算法回顾 [备战蓝桥杯] - 2D 前缀和
-
微积分——什么是导数- 1.1 “derivative”的词源 作为名词,始于15世纪中期,词义为“a derived word or form, a word formed immediately or remotely from another or a root (派生词或派生形式,直接或者由另一个词或词根组成的词)”,由形容司“derivative (派生的)”转化而来。常用词义“that which is derived or deduced from another(由另一个事物派生或演绎而来的事物)”始于1590年代,其数学意义“a derivative function (导数函数)”始于1670年代。 1.2 “derivative”的数学意义来源 Newton(牛顿)将“derivative”称为“Fluxion(流数)”,即流(flow): f′是“流动的(fluent)”(即“流动的功变化的量”)函数f (牛顿用点号(.)代替上撇号(′)( primes);上撇号(′)( primes)是由拉格朗日(Lagrange)在18世纪末引入的)的“流数(fluxion)”。但是随着莱布尼茨的符号和他基于微分(differentials)的方法被普遍采用,牛顿的这个方便的术语就被废弃了。 函数导数的传统名称曾经称为“微分系数(Differential Coefficient)”。之所以使用这个名称是因为当我们将等式写作df(x)=f′(x)dx时f′(x)是dx(微分)的系数。事实上,在18世比和19世纪早期,数学家们对无穷小微分比微分系数更感兴趣。 然而,随着分析变得越来越严谨,注意力转向了导数f′而不是微分f′(x)dx。认识到,函数导数f′是由函数“导出的、衍生出的、演绎出的、推导出的、等等(derived)”,在语法意义上,名词的复数形式是派生于名词的单数形式。在拉丁语中,动词“dērīvāre”词义为“to lead or draw off (water or liquid), to divert, derive (words)(引导或脱去(水或液体),转移、派生(词汇))”,可以解析为由前缀“dē”(词义为“from(来自)”)+“rīvus”(词义为“*, stream of water(小溪、水流)”)构成。这就是对于函数导数f′“导数函数(derived function)”或者“导数(derivative)”的源头。 尽管“derive”流行用于表示导数计算的动词,大部分数学家喜欢用“微分(differentiate)”表示,例如: “针对x微分, 你将会得到相同的函数。” 1.3 “derivative”中文翻译为“导数” 根据前面的叙述,函数导数f′是由函数“导出的、衍生出的、演绎出的、推导出的、等等(derived)”的意义,中文将其翻译为“导数”。 2. “导数(derivative)”的数学意义