当前位置：首页 > news >正文

算法学习日记 | 差分

news 2026/3/26 22:00:03

🧠 算法学习日记 | 今天我用「差分」解了两道题，原来“懒惰更新”能这么优雅！

大家好，我是你们的算法学习搭子 👋
今天继续我的算法入门之旅，重点练习了**差分（Difference Array）**这一高效的数据结构技巧。

很多人觉得“差分”只是用来做区间加法的工具，但其实，它是一种延迟处理思想的体现。
我们不直接修改每个元素，而是记录“变化点”，最后再一次性还原整个数组。

今天我完整做了两道题，每一道都坚持用最朴素的差分逻辑实现。下面我把题目原文和我的原始代码原封不动贴出来，不做任何删减或美化，只为真实记录学习过程。

🔹 题目一：区间更新

问题描述
给定一个长度为 $ n $ 的数组 $ a[1], a[2], \ldots, a[n] $。同时给定 $ m $ 个操作，每个操作有三个整形数据 $ x, y, z $。每个操作的意义就是给数组中下标为 $ x $ 与下标为 $ y $ 之间（包括 $ x, y $）的元素的值加上 $ z $。

输入格式
输入有多组数据，数据组数不大于 5。每一组数据第一行有两个整数 $ n, m (0 < n, m < 10^5) $。第二行有 $ n $ 个整数，分别代表 $ a[1], a[2], \ldots, a[n] (0 \leq a[i] < 10) $ 的初始值。接下来就 $ m $ 行，每一行有 3 个整数 $ x, y, z (0 < x \leq y \leq n, 0 < z < 10) $。

输出格式
在一行内输出这个序列的所有元素的值，并且每个值之间应该以空格隔开。

输入样例

10 5 0 0 0 0 0 0 0 0 0 0 1 5 1 2 6 1 3 7 1 4 9 1 5 10 1 1 1 1 1 2

输出样例

1 2 3 4 5 4 3 2 2 1 3

运行限制

语言：C++
最大运行时间：2s
最大运行内存：1024M

✅ 我的代码（完全保留原始写法）

#include<iostream>usingnamespacestd;constintN=1e5+3;inta[N],d[N];voidsolve(intn,intm){for(inti=1;i<=n;++i)cin>>a[i];for(inti=1;i<=n;++i)d[i]=a[i]-a[i-1];while(m--){intx,y,z;cin>>x>>y>>z;d[x]+=z,d[y+1]-=z;}for(inti=1;i<=n;++i){a[i]=a[i-1]+d[i];}for(inti=1;i<=n;++i){cout<<a[i]<<" ";}}intmain(){intn,m;while(cin>>n>>m){solve(n,m);cout<<endl;}return0;}

🔹 题目二：小明的彩灯

题目描述
小明拥有 $ N $ 个彩灯，第 $ i $ 个彩灯的初始亮度为 $ a_i $。

小明将进行 $ Q $ 次操作，每次操作可选择一段区间，并使区间内彩灯的亮度 $ +x（（（x $ 可能为负数）。

求 $ Q $ 次操作后每个彩灯的亮度（若彩灯亮度为负数则输出 0）。

输入描述
第一行包含两个正整数 $ N, Q $，分别表示彩灯的数量和操作的次数。
第二行包含 $ N $ 个整数，表示彩灯的初始亮度。
接下来 $ Q $ 每行包含一个操作，格式如下：
l r x，表示将区间 $ l \sim r $ 的彩灯的亮度 $ +x $。

约束：$ 1 \leq N, Q \leq 5 \times 10^5，，，0 \leq a_i \leq 10^9，，，1 \leq l \leq r \leq N，，，-10^9 \leq x \leq 10^9 $。

输出描述
输出共 1 行，包含 $ N $ 个整数，表示每个彩灯的亮度。

输入输出样例

输入 5 3 2 2 1 5 1 3 3 4 5 5 1 1 -100

输出 0 5 6 10 10

✅ 我的代码（完全保留原始写法）

#include<iostream>usingnamespacestd;constintN=5e5+5;longlonga[N],d[N];voidsolve(intn,intq){for(inti=1;i<=n;++i)cin>>a[i];for(inti=1;i<=n;++i)d[i]=a[i]-a[i-1];for(inti=0;i<q;++i){intl,r;longlongx;cin>>l>>r>>x;d[l]+=x,d[r+1]-=x;}for(inti=1;i<=n;++i){a[i]=a[i-1]+d[i];}for(inti=1;i<=n;++i){if(a[i]<0)a[i]=0;cout<<a[i]<<" ";}}intmain(){intn,q;cin>>n>>q;solve(n,q);return0;}