差分小结-526互联

应用

区间的修改(对区间内所有元素做相同的修改)和询问

时间复杂度

修改一次区间O(1)

一维差分

D[i]为差分数组，递推公式为a[i]=a[i-1]+D[i]
区间修改需要D[L]+=n,D[R+1]-=n;

二维差分

递推公式为a[i][j]=D[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1]也可以直接累加

for(int i=1;i<=n;++i)
for(int j=1;j<n;++j)
D[i][j+1]+=D[i][j];
for(int j=1;j<=n;++j)
for(int i=1;i<n;++i)
D[i+1][j]+=D[i][j];

修改区间D[x1][y1]+=n;D[x2+1][y1]-=n; D[x1][y2+1]-=1;D[x2+1][y2+1]+=1;

三维差分

递推公式复杂这里直接累加

for (int i=1; i<=A; i++)
        for (int j=1; j<=B; j++)
            for (int k=1; k<C; k++)        //把x、y看成定值，累加z方向
                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++)        //把x、z看成定值，累加y方向
                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++)        //把y、z看成定值，累加x方向
                D[num(i+1,j,k)] += D[num(i,j,k)];

修改区间

for (int i=1; i<=x; i++) {     //用三维差分数组记录区间修改：有8个区间端点
        D[num(x1[i],  y1[i],  z1[i])]   += d[i];
        D[num(x2[i]+1,y1[i],  z1[i])]   -= d[i];
        D[num(x1[i],  y1[i],  z2[i]+1)] -= d[i];
        D[num(x2[i]+1,y1[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];
    }

开三维数组比较占用空间，可以压维

int num(int x,int y,int z) {  
//小技巧：压维，把三维坐标(x,y,z)转为一维的((x-1)*B+(y-1))*C+(z-1)+1
    if (x>A || y>B || z>C) return 0;
    return ((x-1)*B+(y-1))*C+(z-1)+1;
}

二维数组也可以压维(x-1)*B+（y-1)+1