二维和三维差分

　二维差分: hdu6514 给你 p 个红矩阵 一个整数 q，接下来 q 行 每行给出一个蓝矩阵 如果蓝矩阵被完全包含于红矩阵内，输出 "YES"，否则输出 "NO". int main() {

　 int n,m;

　 while(~scanf("%d%d",&n,&m))

　 {

　 int sum[n+2][m+2];

　 for(int i=0;i<=n;i++)

　 {

　 for(int j=0;j<=m;j++)sum[i][j]=0;

　 }

　 int p,q;

　 scanf("%d",&p);

　 while(p--)

　 {

　 int x1,x2,y1,y2;

　 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

　 sum[x1][y1]++;

　 sum[x2+1][y2+1]++;

　 sum[x1][y2+1]--;

　 sum[x2+1][y1]--;

　 }

　 for(int i=1;i<=n;i++)

　 {

　 for(int j=1;j<=m;j++)

　 {

　 sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+sum[i][j];

　 }

　 }

　 for(int i=1;i<=n;i++)

　 {

　 for(int j=1;j<=m;j++)

　 {

　 if(sum[i][j])sum[i][j]=1;

　 }

　 }

　 for(int i=1;i<=n;i++)

　 {

　 for(int j=1;j<=m;j++)

　{

　 sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+sum[i][j];

　 }

　 }

　 scanf("%d",&q);

　 while(q--)

　 {

　 int x1,x2,y1,y2;

　 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

　 int ans=sum[x2][y2]+sum[x1-1][y1-1]-sum[x1-1][y2]-sum[x2][y1-1];

　 if(ans==(x2-x1+1)*(y2-y1+1))puts("YES");

　 else puts("NO");

　 }

　 }

　 return 0; }

　三维前缀和: s[i][j][k]+=s[i-1][j][k]+s[i][j-1][k]+s[i][j][k-1]-s[i-1][j-1][k]-s[i][j-1][k-1]-s[i-1][j][k-1]+s[i-1][j-1][k-1]

　三维差分:

　 s[x1][y1][z1]++;

　 s[x1][y2+1][z2+1]++;

　 s[x2+1][y1][z2+1]++;

　 s[x2+1][y2+1][z1]++;

　 s[x2+1][y1][z1]--;

　 s[x1][y2+1][z1]--;

　 s[x1][y1][z2+1]--;

　 s[x2+1][y2+1][z2+1]--;