一维差分应用场景

一维数组中进行多次 l~r 同时加上一个数值，或者减去一个数值。最后求数组中的每个值时使用前缀和

公式

1.
将i ~ j 中的数值 都加c
add(int i , int j , int c)
{
    b[i] += c;
    b[j + 1] -= c;
}


2.
而其中初始化的时候值的计算：

for(int i = 1 ; i <= n ; i++)
{
    add(i,i,temp) ;  // a[i] = temp;
}

3.
求对应的a[i], 使用前缀和

a[i] = a[i - 1] + b[i];

二维的应用场景：

二维数组中进行多次 从(x1 , y1) -> (x2 , y2)加c的操作。

公式

给(x1 , y1) -> (x2 , y2)的区间加c:
add(x1,y1,x2,y2,c)
{
    b[x1][y1] += c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y1] -= c;
    b[x2 + 1][y2 + 1] += c;
}