本文作者:Zhang, Xuheng
本文分类:编程学习笔记 浏览:1433
阅读时间:888字, 约1-1.5分钟
其实是复习笔记。
前缀和
一般用来求区间和。
一维
- 现在给出一个数列 $a$,要求回答 $m$ 次询问,每次询问下标 $l$ 到 $r$ 的和。
算好前缀和,
```s[r]−s[l−1]``` 就是答案。
#include <bits/stdc++.h>
using namespace std;
int n;
int a[1005],s[1005];
int main() {
cin>>n;
for(int i=1; i<=n; i++) scanf("%d",&a[i]);
s[1] = a[1];
for(int i=2; i<=n; i++) s[i] = s[i-1] + a[i];
int l,r;
cin>>l>>r;
cout<<s[r] - s[l-1]<<endl;
return 0;
}
二维
差分
一维
差分数组的功能是修改区间,查询点。修改 $O(1)$,查询 $O(n)$。
- 给定一个长度为 $n$ 的数列 $a$,有 $q$ 个操作,每次操作给定 $l,r,x$ 表示 $[l,r]$ 区间所有的数都加上 $x$。并求修改后的序列a。
预处理:
c[1]=a[1];
for(int i=2;i<=n;i++)
c[i]=a[i]-a[i-1];
修改:
void update(int l,int r,int x) {
c[l] += x;
c[r+1] -= x;
}
查询:
int sum(int x) {
int ans = 0;
for(int i=1;i<=x;i++)
ans += c[i];
return ans;
}
差分。
#include <bits/stdc++.h>
using namespace std;
int n;
int a[1005],s[1005];
int main() {
cin>>n;
for(int i=1; i<=n; i++) scanf("%d",&a[i]);
s[1] = a[1];
for(int i=2; i<=n; i++) s[i] = a[i] - a[i-1];
for(int i=1; i<=n; i++) printf("%d ",s[i]);
return 0;
}
二维
类比二维前缀和和一维差分,可以简单推测出二维差分的公式:
c[i][j] = a[i][j] − a[i−1][j] − a[i][j−1] + a[i−1][j−1]
关于作者Zhang, Xuheng
- 还没有填写个人简介
- Email: hy23682@126.com
- 注册于: 2020-04-07 05:11:14