差分是前缀和的逆操作
差分可以再O(1)的时间里让区间[x,y]进行加减操作
求出差分数组即可求出操作后的数组
一维差分
例题:HDU1556
for(int i=1;i<=n;i++){ int L,R;cin>>L>>R; d[L]++;d[R+1]--; } for(int i=1;i<=n;i++){ a[i]=a[i-1]+D[i]; cout<<a[i]<<' '; }
二维差分
例题:洛谷P3397
cin>>n>>m; for(int i=1,x,y,a,b;i<=m;i++){ cin>>x>>y>>a>>b; d[x][y]++; d[a+1][b+1]++; d[x][b+1]--; d[a+1][y]--; } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ d[i][j]+=d[i-1][j]+d[i][j-1]-d[i-1][j-1]; cout<<d[i][j]<<' '; } cout<<'\n'; }
三维查分
例题:蓝桥-180
bool check(int x){ for(int i=1;i<=n;i++)D[i]=0; for(int i=1;i<=x;i++){ D[num(x1[i],y[i],z1[i])]+=d[i]; D[num(x2[i]+1,y[i],z1[i])]-=d[i]; D[num(x1[i],y[i],z2[i]+1)]-=d[i]; D[num(x2[i]+1,y[i],z2[i]+1)]+=d[i]; D[num(x1[i],y2[i]+1,z1[i])]-=d[i]; D[num(x2[i]+1,y2[i]+1,z1[i])]+=d[i]; D[num(x1[i],y2[i]+1,z2[i]+1)]+=d[i]; D[num(x2[i]+1,y2[i]+1,z2[i]+1)]-=d[i]; } for(int i=1;i<=A;i++){ for(int j=1;j<=B;j++){ for(int k=1;k<C;k++){ D[num(i,j,k+1)]+=D[num(i,j,k)]; } } } for(int i=1;i<=A;i++){ for(int k=1;k<=C;k++){ for(int j=1;j<B;j++){ D[num(i,j+1,k)]+=D[num(i,j,k)]; } } } for(int j=1;j<=B;j++){ for(int k=1;k<=C;k++){ for(int i=1;i<A;i++){ D[num(i+1,j,k)]+=D[num(i,j,k)]; } } } for(int i=1;i<=n;i++)if(D[i]>s[i])return 1; return 0; }
标签:前缀,int,++,差分,--,例题 From: https://www.cnblogs.com/zhanghx-blogs/p/17229685.html