前缀和 & 差分

前缀和

一维

令 $sum[j]=\sum_{i=1}^{j}a[i]$ ，则 $\sum_{i=L}^{R}a[i]=sum[R]-sum[L-1]$

int main()
{
  int n,m,sum[maxn],a[maxn],l,r;
  sum[0]=0;
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++)
  {
    scanf("%d",&a[i]);
    sum[i]=sum[i-1]+a[i];
  }
  for(int i=1;i<=m;i++)
  {
    scanf("%d%d",&l,&r);
    printf("%d
",sum[r]-sum[l-1]);
  }
  return 0;
}

二维

令 $sum[x][y]=\sum_{i=1}^{x}\sum_{j=1}^{y}a[i][j]$

int main()
{
   int n,m,k,sum[maxn][maxn],a[maxn][maxn];
   scanf("%d%d%d",&n,&m,&k);
   for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
     {
       scanf("%d%d",&a[i][j]);//构造二维前缀和sum[i][j]
       sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
     }
   while(k--)
   {
    int x1,y1,x2,y2;
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);//求坐标为x1,y1,x2,y2的矩形内的数值和
    cout<<sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]<<endl;
   }
   return 0;
}

差分

一维

令 $d[i]=a[i]-a[i-1]$ ，则 $a[i]=\sum_{i=1}^{i}d[i]$

void insert(int l,int r,int c)
{
  d[l]+=c;
  d[r+1]-=c;
}
int main()
{
   cin>>n>>m;
   for(int i=1;i<=n;i++)
   {
     scanf("%d",&a[i]);
     insert(i,i,a[i]);
   }
   while(m--)
   {
     int l, r, c;
     scanf("%d%d%d",&l,&r,&c);
     insert(l,r,c);
   }
   for(int i=1;i<=n;i++) d[i]+=d[i-1];
   for(int i=1;i<=n;i++) printf("%d	",d[i]);
   return 0;      
}

二维

令

void insert(int x1,int y1,int x2,int y2,int c)
{
  b[x1][y1]+=c;
  b[x1][y2+1]-=c;
  b[x2+1][y1]-=c;
  b[x2+1][y2+1]+=c;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
      {
        scanf("%d%d",&a[i][j]);
        insert(i,j,i,j,a[i][j]);
      }
    while(k--)
    {
     int x1,y1,x2,y2,c;
     scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
     insert(x1,y1,x2,y2,c);
    }
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
         b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
    for(int i=1;i<=n;i++)
    {
      for(int j=1;j<=m;j++) printf("%d	",b[i][j]);
      printf("
");
    }
    return 0;    
}