差分数组(简单易懂)

差分数组(简单易懂)一、什么是差分数组?差分数组本质上来说就是一个数组,可以用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.当我们需要单独查询原数组一个点的值的时候,我们不难发现出令Sn为di的前缀和,那么a[i]=Si;3.当我们需要求原数组的前缀和的时候,我们可以设前x项

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

一、什么是差分数组?

差分数组本质上来说就是一个数组,可以用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.当我们需要单独查询原数组一个点的值的时候,我们不难发现出令S_{n}为d[i]的前缀和,那么a[i]=S_{i};

3.当我们需要求原数组的前缀和的时候,我们可以设前x项和为sum_{x},则有:sum_{_{x}}=\sum_{i=1}^{x}a[i]=\sum_{i=1}^{x} \sum_{j=1}^{i}d[i]=\sum_{i=1}^{x}(x-i+1)d[i]

四、例题:

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

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/143800.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号