ACM入门之【差分】

简言之：差分可以O(1)的给一段区间或矩阵加减相等的值

差分的分类：

• 一维差分
• 二维差分
• 树上差分
  • 点差分
  • 边差分

一维差分模板：

const int N=1e5+10;
int s[N];
void add(int l,int r,int c){s[l]+=c,s[r+1]-=c;}
void init(){for(int i=1;i<=n;i++) s[i]+=s[i-1];}

一维差分习题

二维差分模板：

const int N=1010;
int s[N][N],n,m;
void add(int x,int y,int xx,int yy,int c)
{
    s[x][y]+=c;
    s[x][yy+1]-=c;
    s[xx+1][y]-=c;
    s[xx+1][yy+1]+=c;
}
void init(int n,int m)
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) 
            s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}

二维差分习题