大家好，又见面了，我是你们的朋友全栈君。
一、什么是差分数组？
差分数组本质上来说就是一个数组，可以用O(1)的时间处理区间修改。
二、差分数组的定义式
设原数组为a数组，差分数组为d数组，则对于i∈[2,n],都有d[i]=a[i]-a[i-1].
三、差分数组的性质
1.当我们需要更新区间[l,r]时候（仅指加减运算），我们仅仅可以只更新d[l]+=x,d[r+1]-=x;
2.当我们需要单独查询原数组一个点的值的时候，我们不难发现出令
为d[i]的前缀和，那么a[i]=
;
3.当我们需要求原数组的前缀和的时候，我们可以设前x项和为，则有：
四、例题：
AC代码：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
map<int,int>mapp;
int main(){
int n,x,y,z;
cin >> n >> x >> y >> z;
int xx,yy;
for (int i = 1; i <= n; i ++ )
{
cin >> xx >> yy;
mapp[0]+=x;
mapp[xx]=mapp[xx]-x+y;
mapp[yy+1]=mapp[yy+1]-y+z;
}
int maxn=0;
int sum=0;
for(map<int,int>::iterator iter=mapp.begin();iter!=mapp.end();iter++){
sum+=iter->second;
maxn=max(maxn,sum);
}
cout<<maxn;
return 0;
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/143800.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...