差分

• 一维差分(区间所有数加数问题)
• • 描述:
  • Code:
• 二维差分
• • 描述
  • code:

一维差分(区间所有数加数问题)

描述:

可以让一个数组

对其区间每一个数加上一个数

先预处理

后输出的时候

直接一次性输出

Code:

输出的时候 需要做 前缀和处理

void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

 for (int i = 1; i <= n; i ++ ) 
 b[i] += b[i - 1];

二维差分

描述

其实就是对将二维转换成多个一维即可

code:

模板题:
地毯

    scanf("%d%d",&n,&m);
    while(m--)
    {
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        for(int i=x1;i<=x2;i++)
        {
            b[i][y1]++;
            b[i][y2+1]--;
        }

    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            b[i][j]=b[i][j-1]+b[i][j];
            printf("%d ",b[i][j]);
        }
        printf("\n");
    }