企业门户网站开发公司,石龙东莞网站建设,网站建设方面的优劣势分析,j2ee 建设简单网站P2367 语文成绩 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 差分
令a[i]为b[i]数组的前缀和
a[n]b[1]b[2]b[3].....b[n];
a[n-1]b[1]b[2]b[3].....b[n-1];
构造差分数组 b[i]a[i]-a[i-1];
有什么好处 当我们想对a[l]--a[r]范围内所有数据加上一个数x
不必循环 for(i…P2367 语文成绩 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 差分
令a[i]为b[i]数组的前缀和
a[n]b[1]b[2]b[3].....b[n];
a[n-1]b[1]b[2]b[3].....b[n-1];
构造差分数组 b[i]a[i]-a[i-1];
有什么好处 当我们想对a[l]--a[r]范围内所有数据加上一个数x
不必循环 for(int il;ir;i) a[i]x;
直接
b[l]c;//从l-n的范围全部c;
b[r1]-c;//将r1到n范围多加的C减掉
自此我们快速将一个循环才能完成的操作优化 主要是为了以后学二维的差分做铺垫
对于构造差分数组 我们采取 add ()函数
void add(int l,int r,int x){ b[l]x; b[r1]-x; }
for(int i1;in;i){ cina[i]; add(i,i,a[i]);//构造b[i] 差分数组 }
该函数 在首次输入a[i]数组构造差分数组的效果
等价于 b[i]a[i]-a[i-1]
为什么呢
我们传入了两个i
传进add后
相当于
b[i]这个数加上了a[i]
而b[i1]这个数减去了a[i]
///这一部操作是因为 b[i]a[i]-a[i-1] 在我们输入下一个a[i]时
//当前的这个a[i]就是下一个a[i]的”a[i-1]而我们要减去的a[i-1]其实在上一次输入时就已经先减去了
所以读入当前a[i] 只要将b[i](它的值是 -a[i-1] )加上这个a[i]即可
那我为什么不直接写 b[i]a[i]-a[i-1] 其实完全没问题
只是二维差分数组的构造 也采取add 这里先讲了add的原理 以便进一步理解二维差分数组的构造
完整代码
#includeiostream using namespace std; const int N5e610; int a[N],b[N]; void add(int l,int r,int x){ b[l]x; b[r1]-x; } int main(){ int n,m; cinnm; for(int i1;in;i){ cina[i]; add(i,i,a[i]);//构造b[i] 差分数组
//此处的insert 操作的实际效果 //与该语句 b[i]a[i]-a[i-1]; 相同 //初始化 插入差分数组 //使b[i]变成当前 a[i]的差分数组 //b数组为空 将a数组的原始值插入b数组 就是按照差分处理的形式 //初始化b数组的原始缓存 } for(int i0;im;i){ int a,b,c; cinabc; add(a,b,c); //执行增值操作 //但是只是对差分数组 进行了增值操作 //a数组是b数组的前缀和数组 //而b数组 就是a数组 未经扫描的冗沉 缓存 //我们对b数组的操作 只是暂时记录了增减情况 还没把这个情况汇报给a数组 } for(int i1;in;i){ a[i]a[i-1]b[i]; //扫描一编操作的增减值 //计算前缀和 } int minna[1]; for(int i1;in;i){ minnmin(a[i],minn); } coutminn; return 0; } 举个例子模拟一下缓存池情况
对于以下代码
插入改组数据 /* 6 3 1 2 2 1 2 1 1 3 1 3 5 1 1 6 1*/
#includeiostream using namespace std; const int N100010; int a[N],b[N]; int n,m; void insert(int l,int r,int c){ b[l]c; //b[l]到n的位置加上 c b[r1]-c; //减去 上一步中多加的【r1】到n的部分 cout当前缓存池 is ; for(int i1;in;i){ coutb[i] ; } coutendl; } int main(){ cinnm; for(int i1;in;i){ cina[i]; } for(int i1;in;i){ insert(i,i,a[i]); //此处的insert 操作的实际效果 //与该语句 b[i]a[i]-a[i-1]; 相同 //初始化 插入差分数组 //使b[i]变成当前 a[i]的差分数组 //b数组为空 将a数组的原始值插入b数组 就是按照差分处理的形式 //初始化b数组的原始缓存 } while(m--){ int l,r,c; cinlrc; insert (l,r,c); //执行增值操作 //但是只是对差分数组 进行了增值操作 //a数组是b数组的前缀和数组 //而b数组 就是a数组 未经扫描的冗沉 缓存 //我们对b数组的操作 只是暂时记录了增减情况 还没把这个情况汇报给a数组 } for(int i1;in;i){ a[i]a[i-1]b[i]; //扫描一编操作的增减值 //计算前缀和 } for(int i1;in;i){ //couta[i] ; } return 0; }
缓存池情况
