前缀和与差分

#define getsum(k,r) (k?sum[r]-sum[k-1]:sum[r])//获得k到r间的和,宏定义更加的方便
int get_sum(int k, int r,int *sum)
{
  if (k == 0)
  {
    return sum[r];
  }
  else
  {
    return sum[r] - sum[k - 1];
  }
}
int main()
{
  const int n = 5;
  int arr[5] = { 1,3,7,5,2 };
  int sum[5];//sum原来记录前缀和
  sum[0] = arr[0];//0单独记录
  int i = 1;
  for (i = 1; i < 5; i++)
  {
    sum[i] = sum[i - 1] + arr[i];
  }
  //获取前缀和
  //获得k到r的和
  printf("%d", getsum(2, 4));//得到2-4的区间和，使用宏的方法
  printf("%d->", get_sum(1, 3,sum));//
  return 0;
}

//一开始
int d[6]={0};//比arr多开辟一个空间原来r+1
void add(int l,int r,int v)
{ 
  d[l] += v;//在l-r的区间上都加上一个val，就是d[l]+v,加了之后对后面的所有值都加了一个val，但是d[r+1]-v,把后面加起来的v都抵消掉，只保证r-l间改变
  d[r + 1] -=v;
}
int main()
{
memset(d,0,sizeof(d));
  int arr[5] = { 1,3,7,5,2 };
  add(2, 4, 5);//2-4都+5
  add(1, 3, 2);
  add(0, 2, -3);
  //将d取0进行操作 
  int i;
  for (i = 1; i < 5; i++)
  {//对d进行做前缀和，就是要对arr改变的值
    d[i] += d[i - 1];
  }
  for (i = 0; i < 5; i++)
  {//将d加到arr上
    arr[i] += d[i];
    printf("%d ", arr[i]);
  }
  memset(d, 0, sizeof(d));//用完了之后要将d还原为0，以免后续有重新再用d
  return 0;
}

int main()
{
  int matrix[5][5] = { {3,0,1,4,3},{5,6,3,2,1},{1,2,0,1,5},{4,1,0,1,7},{1,0,3,0,5} };
  //计算二维数组的前缀和
  int sum[5][5];//sum[i][j]是从s[0][0]到s[i][j]形成的矩阵中进行前缀和相加
  int i, j;
  //计算前缀和，这里要用公式计算
  for (i = 0; i < 5; i++)
  {
    for (j = 0; j < 5; j++)
    {
      sum[i][j] = matrix[i][j];
      if (i - 1 > 0)
      {
        sum[i][j] += sum[i - 1][j];
      }
      if (j - 1 > 0)
      {
        sum[i][j] += sum[i][j - 1];
      }
      if (i - 1 > 0 && j - 1 > 0)
      {
        sum[i][j] -= sum[i - 1][j - 1];
      }
    }
  }
  //计算区间和
  //如[2,2]->[3,3];
  int row1 = 2, col1 = 2, row2 = 3, col2 = 3;
  int ans = sum[row2][col2];
  if (col1 - 1 > 0)
  {
    ans -= sum[row2][col1 - 1];
  }
  if (row1 - 1 > 0)
  {
    ans -= sum[row1 - 1][col2];
  }
  if (col1 - 1 > 0 && row1 - 1 > 0)
  {
    ans += sum[row1 - 1][col1 - 1];
  }
  printf("%d", ans);
  return 0;
}

int d[5][5];
//二维前缀和
//二维差分
void add(int x1, int y1, int x2, int y2, int v)
{
  d[x1][y1] += v;
  d[x2 + 1][y1] -= v;
  d[x1][y2 + 1] -= v;
  d[x2 + 1][y2 + 1] += v;
}
void print(int** d, int x, int y)
{
  int i, j;
  for (i = 0; i < x; i++)
  {
    for (j = 0; j < y; j++)
    {
      printf("%d ", d[i][j]);
    }
    printf("\n");
  }
}
int main()
{
  int matrix[3][4] = { {1,5,6,8},{9,6,7,3},{5,3,2,4} };
  memset(d, 0, sizeof(d));
  add( 0, 0, 2, 1, 3);
  add(1, 1, 2, 2, -1);
  int i, j;
  for (i = 0; i < 3; i++)
  {
    for (j = 0; j < 4; j++)
    {
      matrix[i][j] += d[i][j];
      printf("%d ", matrix[i][j]);
    }
    printf("\n");
  }
  return 0;
}