二维前缀和与差分

对于一个二维数组a定义数组为数组a的前缀和数组，可以理解为一个左上矩阵的矩阵和 
//为了避免数组越位，下标从1开始
for(int i=1;i<=n;++i)
{
    for(int j=1;j<=m;++j)//可以只用一个数组，这里为了看的清楚区分了s与a
    {
        s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
    }
}
定义数组
为了避免数组越位，下标从1开始
for(int i=n;i;--i)
{
    for(int j=m;j;--j)//倒着for可以只用一个数组，这里是为了看的清楚区分了d与a
    {
        d[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];
    }
}

静态数组的求和问题


这个是利用了简单的容斥原理，纸上画画图就能理解
因为s[i][j]是一个左上矩形的矩阵和，所以这个矩阵在减去与矩阵后，它们共有的部分被减了两次，所以再加上一次。 
int sum(int l1,int r1,int l2,int r2)
{
    return s[r1][r2]-s[l1-1][r2]-s[r1][l2-1]+s[l1-1][l2-1];
}

进行m次区间修改后的静态单点求值问题

推导过程类似一维的前缀和与差分，其实就是反过来考虑差分数组对原数组的影响是一个后缀影响（这里可以理解为影响整个右下角矩阵） 
void add(int l1,int r1,int l2,int r2,int x)
{
    d[l1][l2]+=x;
    d[r1+1][l2]-=x;
    d[l1][r2+1]-=x;
    d[r1+1][r2+1]+=x;
}
同理，d数组可以靠一次前缀和操作还原为原数组，如果是矩阵求和问题还可再做一遍前缀和。

高维前缀和（SOSDP）