前缀和
2020-05-04 16:00:20来源:博客园 阅读 ()
前缀和
目录
- 前缀和
- 一维前缀和
- Skips
- 模板题
- 代码
- 二维前缀和
- Skips
- 模板题
- 代码
前缀和
一维前缀和
Skips
-
快速计算一个区间内数的和 [l,r]
-
定义一个数组 ,下标要从1 开始 ,边界值 定义 s[0]=0 (如果是全局变量 的 数组 不必再 初始化,若不是 记得初始化s[0]=0),记录 s[i] 为 数组 a 中第 i个数之前所有数的和
-
```s[i] = s[i-1] + a[i];// 递推公式 这里面有 i-1 所以 当 l=1 的时候 (就是从第一个数开始算的话)`下标会为 i-1 那么i-1 就得是 0 不然数就不对 ``
-
具体计算 使用 是
s[r]-s[l-1]
因为 s[]数组记录的是 多少个数 的和 相减 正好剩下 两个下标相差的值 注意这里是l-1
如果是 l 的话那么 剪完之后是 s[l+1] 到 s[r] 的值 中间a[l] 的在两个前缀里面都有,就被减掉了。
模板题
输入一个长度为n的整数序列。
接下来再输入m个询问,每个询问输入一对l, r。
对于每个询问,输出原序列中从第l个数到第r个数的和。
输入格式
第一行包含两个整数n和m。
第二行包含n个整数,表示整数数列。
接下来m行,每行包含两个整数l和r,表示一个询问的区间范围。
输出格式
共m行,每行输出一个询问的结果。
数据范围
1≤l≤r≤n1≤l≤r≤n,
1≤n,m≤1000001≤n,m≤100000,
?1000≤数列中元素的值≤1000?1000≤数列中元素的值≤1000
输入样例:
5 3
2 1 3 6 4
1 2
1 3
2 4
输出样例:
3
6
10
代码
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N],s[N]; // s[0]=0;
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i]; //数组 a存完之后 在 存s数组
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]; // 递推公式
while(m--)
{
int l,r;
cin>>l>>r;
cout<<s[r]-s[l-1]<<endl; // 输出的时候下标 右端点 数值 减一
}
return 0;
}
二维前缀和
Skips
-
应用:
- 给出一个坐标,求出 以 该坐标为右下角的矩阵的元素的和
- 给出两个坐标,求出 以 小的坐标为 左上角,大的坐标为右上角 的矩阵元素的和
-
核心
-
第一个应用 : 求和 的具体操作
// 利用了容斥原理 通过 分块的思想 // 先读入元素 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j]; 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]+a[i][j]; // 加的时候 多加的 要减去 不要忘了 a[i][j]
-
第二个应用: 做差 的具体操作
int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2; cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<<endl; // 减的时候多 减了要加回来 return 0;
-
模板题
输入一个n行m列的整数矩阵,再输入q个询问,每个询问包含四个整数x1, y1, x2, y2,表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数n,m,q。
接下来n行,每行包含m个整数,表示整数矩阵。
接下来q行,每行包含四个整数x1, y1, x2, y2,表示一组询问。
输出格式
共q行,每行输出一个询问的结果。
数据范围
1≤n,m≤10001≤n,m≤1000,
1≤q≤2000001≤q≤200000,
1≤x1≤x2≤n1≤x1≤x2≤n,
1≤y1≤y2≤m1≤y1≤y2≤m,
?1000≤矩阵内元素的值≤1000?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
代码
#include<iostream>
using namespace std;
const int N=1e3+10;
int a[N][N],s[N][N];
int n,m,q;
int main()
{
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
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]+a[i][j];
while(q--)
{
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<<endl;
}
return 0;
}
原文链接:https://www.cnblogs.com/xuexijiaoliu/p/12826549.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:博弈--尼姆博弈
下一篇:单调队列模板【附例题】
- 二叉搜索树_BST 2020-05-30
- 第八章 标准模板库STL(一) 2020-04-04
- 第七章 2.泛型编程(模板) 2020-04-04
- 第七章 1.输入输出与模板 2020-04-04
- 第五章 继承与派生 2020-04-04
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash