算法笔记（六）：差分法

2023-12-21 00:31| 来源: 网络整理| 查看: 265

（6）差分法

一、差分

1、介绍

2、定义

3、差分与前缀和

二、一维差分

1、定义

2、作用

3、方法

接下来是实战演练！！！

三、二维差分

1、定义

2、作用

3、方法

接下来是实战演练！！！

结论

写在最后！！！

一、差分 1、介绍

一般地，差分主要用于让一个序列某一特定范围内的所有值都加上或减去一个常数。

所以差分往往应用于线性的场合，即一维数组的环境，但是除此之外，差分还可以应用于二维数组，但是相比较一维数组，应用的较少。

2、定义

差分可以简单的看成序列中每个元素与其前一个元素的差。

3、差分与前缀和 const int N = 100010; int n; //n数组长度 //定义两个一维整形数组 a为原数组，b为差分数组 int a[N],b[N]; //根据定义可知 b[i] = a[i] - a[i-1]; //稍微具体 b[1] = a[1]; b[2] = a[2] - a[1]; b[3] = a[3] - a[2]; ... b[i] = a[i] - a[i-1]; //转化一下，求数组b的前缀和,根据上面公式可得 b[1]+b[2]+b[3]+...+b[i] = a[1]+(a[2]-a[1])+(a[3]-a[2])+...+(a[i]-a[i-1]) = a[i] //由此可知，原序列为差分序列的前缀和序列 a[i] = b[1]+b[2]+b[3]+...+b[i];

一般地，我们认为原序列就是差分序列的前缀和，所以把差分看做前缀和的逆运算

二、一维差分 1、定义

一维差分是指给定一个长度为n的序列a，要求支持操作pro(l,r,c)表示对a[l]~a[r]区间上的每一个值都加上或减去常数c，并求修改后的序列a。

2、作用

让一个序列中某个区间内的所有值均加上或减去一个常数。

可以将对a数组任意区间的同一操作优化到O(1)。

//区间[l,r]中的所有值都加上常数c b[l] += c; b[r+1] -= c; //上边语句实现原理 b相当于a的辅助数组 //把a序列分为[1,l-1],[l,r],[r+1,n]三部分,由差分定义和与前缀和关系可得 a[l-1] = b[1]+b[2]+...+b[l-1]; //b[1]~b[l-1]中所有值都未改变，a[l-1]也不变 a[l] = b[1]+b[2]+...+b[l-1]+b[l]; //b[1] += c,所以a[l] += c a[l+1] = b[1]+b[2]+...+b[l-1]+b[l]+b[l+1]; //b[1] += c,所以a[l+1] += c ... //一直到 a[r] = b[1]+b[2]+...b[l]+...+b[r]; //b[1] += c,所以a[l+1] += c a[r+1] = b[1]+b[2]+...b[l]+...+b[r]+b[r+1]; //b[l] += c,b[r+1] -= c;所以a[r+1]不变 //所以由此可知上面的两个语句（b[l] += c;b[r+1] -= c）可以实现a数组在区间[l,r]内的所有值都加上了常数c 3、方法

对a数组区间[l,r]同时加上c的操作可转化为：

void insert(int l, int r, int c) { b[l] += c; b[r+1] -= c; } while(m--) { int l,r,c; scanf("%d%d%d",&l,&r,&c); insert(l,r,c); }

对b数组求前缀和即可得到原数组a：

for(int i = 1; i

【本文地址】

公司简介

联系我们