前缀和与差分
前缀和与差分
差分数组的定义
差分数组 diff 是一个长度为 n 的数组，其中 diff[i] 表示原始数组 arr 中的相邻元素之差。形式化地，diff[i] = arr[i] - arr[i-1]。
利用差分数组进行区间更新
差分数组的一个主要应用是进行区间更新。通过对差分数组进行操作，可以在常数时间内完成对原始数组中某个区间的增量更新。具体步骤如下：
- 对差分数组进行更新：对于区间
[l, r]，在差分数组中diff[l]增加val，而diff[r+1]减少val。 - 利用更新后的差分数组构建新的数组：从差分数组恢复原始数组
arr。遍历diff，依次累加每个差分值，得到新的数组。
这种方法的关键在于通过更新差分数组，将区间更新的操作转化为差分数组的单点更新，从而避免了对整个区间的遍历。
int a[N];// 原数组
int diff[N];// 差分数组
int sum[N];// 前缀和数组
int diff[i];// 差分数组
// sum[i]=sum[i-1]+a[i]diff[i]=a[i]-a[i];
// 可得如下性质
- 对原数组的差分数组求前缀和 -> 原数组
- 对原数组的前者和数组求差分 -> 原数组
要点
利用差分和前缀和，可以离线快速O(1)进行区间修改和查询，如区间[l,r]上各个元素加x，随后查询区间某点的值。
使用示例，csp 202203-2 出行计划
// 202203-2
#include <bits/stdc++.h>
using namespace std;
const int N=200010;
int n,m,k;
int diff[N];
int main()
{
cin>>n>>m>>k;
int mx=0;
for(int i=1;i<=n;++i){
int in,c;
cin>>in>>c;
// 打疫苗区间[in-c-k+1,in-k]
// t+k<=in<=t+k+c-1 => t<=in-k t>=in-c-k+1
diff[max(1,in-c-k+1)]+=1;// max是为了防止下标为负
diff[max(1,in-k+1)]-=1;
mx=max(mx,in-k+1);
}
for(int i=1;i<=mx;++i) {
diff[i]+=diff[i-1];
}
for(int i=1;i<=m;++i){
int q;
cin>>q;
cout<<diff[q]<<endl;
}
return 0;
}
原文地址：https://blog.csdn.net/jokerMingge/article/details/135618042
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！