承德网站网站建设,wordpress幻灯片插件使用,短期网页设计师培训,程序员前端和后端的区别#x1f9e0; 算法学习日记 | 今天我用「差分」解了两道题#xff0c;原来“懒惰更新”能这么优雅#xff01; 大家好#xff0c;我是你们的算法学习搭子 #x1f44b; 今天继续我的算法入门之旅#xff0c;重点练习了**差分#xff08;Difference Array#xff09;**这… 算法学习日记 | 今天我用「差分」解了两道题原来“懒惰更新”能这么优雅大家好我是你们的算法学习搭子 今天继续我的算法入门之旅重点练习了**差分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✅ 我的代码完全保留原始写法#includeiostreamusingnamespacestd;constintN1e53;inta[N],d[N];voidsolve(intn,intm){for(inti1;in;i)cina[i];for(inti1;in;i)d[i]a[i]-a[i-1];while(m--){intx,y,z;cinxyz;d[x]z,d[y1]-z;}for(inti1;in;i){a[i]a[i-1]d[i];}for(inti1;in;i){couta[i] ;}}intmain(){intn,m;while(cinnm){solve(n,m);coutendl;}return0;} 题目二小明的彩灯题目描述小明拥有 $ N $ 个彩灯第 $ i $ 个彩灯的初始亮度为 $ a_i $。小明将进行 $ Q $ 次操作每次操作可选择一段区间并使区间内彩灯的亮度 $ xx $ 可能为负数。求 $ Q $ 次操作后每个彩灯的亮度若彩灯亮度为负数则输出 0。输入描述第一行包含两个正整数 $ N, Q $分别表示彩灯的数量和操作的次数。第二行包含 $ N $ 个整数表示彩灯的初始亮度。接下来 $ Q $ 每行包含一个操作格式如下l r x表示将区间 $ l \sim r $ 的彩灯的亮度 $ x $。约束$ 1 \leq N, Q \leq 5 \times 10^50 \leq a_i \leq 10^91 \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✅ 我的代码完全保留原始写法#includeiostreamusingnamespacestd;constintN5e55;longlonga[N],d[N];voidsolve(intn,intq){for(inti1;in;i)cina[i];for(inti1;in;i)d[i]a[i]-a[i-1];for(inti0;iq;i){intl,r;longlongx;cinlrx;d[l]x,d[r1]-x;}for(inti1;in;i){a[i]a[i-1]d[i];}for(inti1;in;i){if(a[i]0)a[i]0;couta[i] ;}}intmain(){intn,q;cinnq;solve(n,q);return0;} 我的思考这两道题虽然看起来不同但都用了差分的核心思想区间更新每次操作只在d[x] z和d[y1] - z处做标记避免逐个修改。小明的彩灯同理先建差分数组再批量还原最后判断是否为负。你会发现差分的本质是“懒惰更新”—— 不立即改变所有元素而是记录“变化起点”和“变化终点”。这种思想在大数据场景中特别有用。比如有 100 万个灯泡要执行 1 万次区间加法 → 用暴力会超时用差分只需 $ O(n m) $而且差分可以扩展到二维、多维甚至用于解决“区间最小值”、“区间最大值”等问题结合线段树。✅ 总结差分的核心是记录变化点延迟还原适用于多次区间加减操作的问题时间复杂度每次操作 $ O(1) $最后还原 $ O(n) $关键在于构建差分数组d[i] a[i] - a[i-1]还原方式a[i] a[i-1] d[i]注意边界d[y1] - z防止越界