1. 首页首页
  2. 编程汇总编程汇总

2025年差分数组（简单易懂）

编程汇总 • • 阅读 68

差分数组（简单易懂）一 什么是差分数组 差分数组本质上来说就是一个数组 可以用 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 当我们需要单独查询原数组一个点的值的时候

一、什么是差分数组？

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

#include 

#include 

#include 

using namespace std;

mapmapp;

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::iterator iter=mapp.begin();iter!=mapp.end();iter++){

        sum+=iter->second;        

        maxn=max(maxn,sum);

    }

    cout<
    return 0;

}
编程小号
上一篇 2025-07-06 11:01
下一篇 2025-03-04 13:06

相关推荐

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