网站建设安全问题,湖南网站建设 要上磐石网络,合购8登录WordPress,云龙网站开发作者#xff1a;指针不指南吗 专栏#xff1a;算法篇 #x1f43e;合理规划时间与精力#x1f43e; 1.什么是差分#xff1f;
与前缀和是反函数
原数组a a1 , a2 , a3 , a4 , a5 , a6 , a7 构造数组b a1b1; a2b1b2; a3b1b2b3; … aib1b2b3…bi; 构造一个b数组使得#… 作者指针不指南吗 专栏算法篇 合理规划时间与精力 1.什么是差分
与前缀和是反函数
原数组a a1 , a2 , a3 , a4 , a5 , a6 , a7 构造数组b a1b1; a2b1b2; a3b1b2b3; … aib1b2b3…bi; 构造一个b数组使得他的前缀和是 a
则b就是a的差分。 2.怎么求差分
差分b , 前缀和 a;
第一种
for(int i1;in;i){cina[i];b[i]a[i]-a[i-1];
}第二种 利用函数在问题具体操作时保持一致
void insert(int l,int r,int c)
{b[l]c;b[r1]-c;
}for(int i1;in;i){cina[i];insert(i,i,a[i]); //原来 b中都是0现在插上
}3.差分有什么用
对一段区间 [ l , r ] 的每个数加上 c每个数多少 差分 b[ l ] c 则 a[ l ~ n ] 全部都加上 c ,因为a[l]...b[l] ,a[l1]...b[l]b[l1] 但是注意 r 之后的元素也都加上 c 了这个不是我们想要的所以打个补丁 令 b[ r 1 ] - c ; 优点是时间复杂度为线性的
#includeiostream
using namespace std;const int N100010;
int a[N],b[N];int n,m; //n 数组元素个数m 表示操作次数void insert(int l,int r,int c){b[l]c; //对差分cb[r1]-c; //补丁
}int main(){cinnm;for(int i1;in;i){cina[i];insert(i,i,a[i]); //差分b 数组}while(m--){int l,r,c; //对差分 b 操作cinlrc; insert(l,r,c); //对区间进行元素进行操作}for(int i1;in;i){ //求出原数组即前缀和aa[i]a[i-1]b[i];couta[i] ;}return 0;
} 4.进阶 二维差分 黄色部分(x1,y1),(x2,y2)内的每个数加上 c 黄色 c (红色顶点c) - (绿色顶点 - c ) - ( 粉色顶点 - c ) ( 混合 色顶点) 差分处理 b [ x1 ] [ y1 ] c ; b [ x1 ] [ y2 - 1 ] - c ; b [ x2 ] [ y1 - 1 ] - c ; b [ x2 - 1 ] [ y2 - 1 ] c ; 代码实现
#include iostreamusing namespace std;const int N 1010;int n, m, q;
int a[N][N], b[N][N];void insert(int x1, int y1, int x2, int y2, int c)
{b[x1][y1] c;b[x2 1][y1] - c;b[x1][y2 1] - c;b[x2 1][y2 1] c;
}int main()
{scanf(%d%d%d, n, m, q);for (int i 1; i n; i )for (int j 1; j m; j ){scanf(%d, a[i][j]);insert(i, j, i, j, a[i][j]);}while (q -- ){int x1, y1, x2, y2, c;cin x1 y1 x2 y2 c;insert(x1, y1, x2, y2, c);}for (int i 1; i n; i ){for (int j 1; j m; j ){b[i][j] b[i - 1][j] b[i][j - 1] - b[i - 1][j - 1];printf(%d , b[i][j]);}puts( );}return 0;
}
