差分数组（简单易懂）

全栈程序员站长

发布于 2022-08-31 09:51:40

3010

发布于 2022-08-31 09:51:40

文章被收录于专栏：全栈程序员必看全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

一、什么是差分数组？

差分数组本质上来说就是一个数组，可以用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项和为

，则有：

四、例题：

AcWing 1952. 金发姑娘和 N 头牛

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;
}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/143800.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年5月2，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法