要对原数组a[N]进行修改与查询，需要用到前缀和数组和差分数组
diff求和——>a 求和——>prefix

diff<——a差分<——prefix差分

一维前缀和与差分

前缀和

前缀和可用于求指定区间的和

  1. 求出前缀和数组
1
前缀和数组的计算:prefix[i] = prefix[i-1] + arr[i] (此处及下文写法i均从1开始，以防止越界问题)
  1. 得出区间和
1
2
由前缀和的可加性:sum[1,k] + sum[k+1,n] = sum[1,n]
得到sum[l,r] = sum[1,r] - sum[1,l-1]，即sum=prefix[r]-prefix[l-1]

差分

差分可用于修改指定区间的值

  1. 求出差分数组
1
diff[i] = a[i] - a[i-1]，它具有两个性质，一是可以通过求和得到a[i]，二是可以对后缀区间进行修改
  1. 对指定区间[l,r]的值进行修改
1
2
diff[l] += x;
diff[r + 1] -= x;
  1. 求出diff的前缀和数组，得到修改后的数组
1
a[i] = a[i-1] + diff[i]

二维前缀和与差分

利用数形结合，前缀和可认为是数组向前拓展/向前的射线涉及的区间的和，差分可认为是数组向后拓展/向后的射线涉及的区间的修改

前缀和

  1. 求出前缀和数组
1
2
3
4
5
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + arr[i][j];
    }
}
  1. 得出区间和
1
2
对于指定区间，设左上角为(x1, y1)，右下角为(x2, y2)
sum = prefix[x2][y2] - prefix[x2][y1-1] - prefix[x1-1][y2] + prefix[x1-1][y1-1];

差分

  1. 求出差分数组
1
2
3
4
5
6
7
8
9
10
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        d[i][j] = arr[i][j] - arr[i][j-1] - arr[i-1][j] + arr[i-1][j-1];
    }
}
or
{d[i][j] += a[i][j];
d[i + 1][j] -= a[i][j];
d[i][j + 1] -= a[i][j];
d[i + 1][j + 1] += a[i][j];}
  1. 对指定区间[(x1,y1),(x2,y2)]的值进行修改
1
2
3
4
d[x1][y1] += c;
d[x2 + 1][y1] -= c;
d[x1][y2 + 1] -= c;
d[x2 + 1][y2 + 1] += c;
  1. 求出diff的前缀和数组，得到修改后的数组
1
2
3
4
5
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        arr[i][j] = arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1] + d[i][j];
    }
}