算法基础班–第一章–11.一维差分模板
算法模板
你真的看懂 y老师的差分代码的模板了吗???
y老师的基础课视频里面讲的一维差分模板 中代码 insert()函数 “可能没讲清楚233333”
下面是我的理解:
下面是 y老师的代码:
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int a[N], b[N];
void insert(int l, int r, int c) {
b[l] += c;
b[r + 1] -= c;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) insert(i, i, a[i]);
while (m--) {
int l, r, c;
scanf("%d%d%d", &l, &r, &c);
insert(l, r, c);
}
for (int i = 1; i <= n; i++) b[i] += b[i - 1];
for (int i = 1; i <= n; i++) printf("%d ", b[i]);
return 0;
}
老师上课讲b数组(差分数组)的构造方式不重要,可以不管,但是他自己却偷偷用了。。。
原数组: a1, a2, a3, …, an
构造数组:b1, b2, b3, …, bn 使得 ai = b1 + b2 + b3 + … + bi(a数组就称为b数组的前缀和数组)
一种构造方式
b1 = a1, ----> a1 = b1
b2 = a2 - a1, ----> a2 = b1 + b2
b3 = a3 - a2, ----> a3 = b1 + b2 + b3
… .....
… .....
b(n) = a(n) - a(n-1) ----> an = b1 + b2 + b3 + … + bn
y老师:假设已经构造出了 b 差分数组,只需对b数组求一遍前缀和,即可求得a数组,因此只要有b数组,就可以在O(n)时间内得到a数组。
后面的 b[l] + c 和 b[r + 1] - c 怎么来的,我就不再讲了,y 老师讲得很清楚了!
y老师写代码前补充了一句话:
原数组是a1, a2, a3, …, an, 可假设a数组初始时全是0, 立即推 ==> 差分数组b也全是0, 而给的a数组不是0,我们可以看作是进行了n次插入(insert)操作。
a1, insert(1,1,a[1])
a2, insert(2,2,a[2])
a3, insert(3,3,a[3])
…,
an, insert(n,n,a[n])
void insert(int l, int r, int c) {
b[l] += c;
b[r + 1] -= c;
}
for (int i = 1; i <= n; i++) insert(i, i, a[i]);
这样的操作能理解,但是和差分数组有什么关系呢??
假设 a[] = {1, 3, 2, 1, 4}
我们把 a 数组带入代码中走一遍,看看结果(注意 b数组是全局变量,所以默认值全为0)
b1 = b1 + a1 = 0 + 1 = 1*****
b2 = b2 - a1 = 0 - 1 = -1
b2 = b2 + a2 = -1 + 3 = 2*****
b3 = b3 - a2 = 0 - 3 = -3
b3 = b3 + a3 = -3 + 2 = -1*****
b4 = b4 - a3 = 0 - 2 = -2
b4 = b4 + a4 = -2 + 1 = -1*****
b5 = b5 - a4 = 0 - 1 = -1
b5 = b5 + a5 = -1 + 4 = 3*****
b6 = b6 - a5 = 0 - 4 = -4
请注意带*****的就是构造出来的b差分数组!!!可以将b数组求前缀和 它就是a 数组了
for (int i = 1; i <= n; i++) b[i] += b[i - 1];
将b数组带入上面的代码
b1 = b1 + b0 —> a1
b2 = b2 + b1 —> a2
b3 = b3 + b2 = b3 + b2 + b1 —> a3
.....
.....
这里y老师把y数组变成自己的前缀和,代码可读性不好!(也可能是我菜。。。)用a数组表示会更容易理解
比如这位童鞋的代码可读性比较好!hhhhhhhh
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=a[i]-a[i-1]; //构建差分数组
}
int l,r,c;
while(m--)
{
scanf("%d%d%d",&l,&r,&c);
b[l]+=c; //将序列中[l, r]之间的每个数都加上c
b[r+1]-=c;
}
for(int i=1;i<=n;i++)
{
a[i]=b[i]+a[i-1]; //前缀和运算
printf("%d ",a[i]);
}
return 0;
}
作者:z林深时见鹿
链接:https://www.acwing.com/solution/content/26588/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
厉害
原来全局变量的值是零┭┮﹏┭┮,tql
最后几句,y数组笔误了吧
感谢大佬!!!
我觉得很牛
好评
代码执行是,键盘键入长度为n数组后,就开始执行insert操作了,所有原来的差分关系被打破,第二次又把原来b数组中的某一个覆盖,然后右形成差分,进行了偶数次,所有原来还是差分
orzorz%%%%%%%
赞!
赞
看视频还有点懵懵懂懂,看你的题解瞬间清晰了,感谢大佬!!!
我懂了…orz我就说为啥二维差分就必须写insert了....二维差分不是a[i][j]和前两个数的差吗?然后我就自己推导出来了一个, b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]; 但是不知道为啥过不去..
就跟这里的两行差分数组和前缀和运算一样呀…是我理解有误吗www
牛啊
牛