前缀和与差分

---

---

前缀和

一维前缀和

板子题：https://www.acwing.com/activity/content/problem/content/829/

公式

$$S[i]=a[i]+S[i-1]$$

CODE

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1e5 + 10;
int n, m, l, r;
int a[N], s[N];int main()
{cin >> n >> m;for(int i = 1; i <= n; ++i){scanf("%d", &a[i]);s[i] = s[i - 1] + a[i];}while(m--){cin >> l >> r;printf("%d\n", s[r] - s[l - 1]);}
}

---

二维前缀和

板子题：https://www.acwing.com/activity/content/problem/content/830/

公式

$$S[i][j]=S[i-1][j]+S[i][j-1]-S[i-1][j-1]+a[i][j]$$

CODE

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1010;
int n, m, q;
int x1, x2, y1, y2;
int a[N][N], s[N][N];int main()
{cin >> n >> m >> q;for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j){scanf("%d", &a[i][j]);s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];}while (q -- ){cin >> x1 >> y1 >> x2 >> y2;printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);}
}

---

差分

一维差分

板子题：https://www.acwing.com/activity/content/problem/content/831/

思路

差分其实是前缀和的逆运算，我们假想有一个数组b[]，它的前缀和是数组a[]，也就是说：
$$b[i]=a[i]-a[i-1]$$

作用

这个b[]数组有什么用呢？
在我们对a[]的元素进行加减操作时，如果采用遍历a[]的方法，时间是 $o(N)$ 的，但是如果我们用b[]对其优化可以使时间复杂度降到 $o(1)$。

对a[]的 $[i,j]$ 段进行+k操作，我们可以在 b[i] + k并在b[j + 1] - k。当我们对b[]求前缀和时，从i开始的每个元素都会+k，但是我们只要加到a[j]就结束了，所以在a[j + 1]进行归位。

CODE

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1e5 + 10;
int n, m;
int l, r, c;
int a[N], b[N];void insert(int l, int r, int c){b[l] += c;b[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 -- ){cin >> l >> r >> c;insert(l, r, c);}for(int i = 1; i <= n; ++i) printf("%d ", b[i] += b[i - 1]);
}

整个差分数组的精髓就在于insert()函数，非常巧妙啊，尤其是在读入阶段对b[]数组进行初始化时的操作，这个操作的意义如下：

来源：https://www.acwing.com/activity/content/code/content/39799/

---

二维差分

板子题：https://www.acwing.com/activity/content/problem/content/832/

思路

答题思路跟一维差分差不多，借鉴二维前缀和的操作我们可以得到以下公式：
$$a[i][j]=b[i][j]-b[i-1][j]-b[i][j-1]+b[i-1][j-1]$$

那我们插入函数该怎么写呢？
一样的原理：
$$\begin{gathered} b[x1][y1]+=c \\ b[x2+1][y1]-=c \\ b[x1][y2+1]-=c \\ b[x2+1][y2+1]+=c \end{gathered}$$

CODE

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;int n, m, q;
const int N = 1010;
int a[N][N], b[N][N];
int x1, y1, x2, y2, c;void insert(int x1, int y1, int x2, int y2, int c){b[x1][y1] += c;b[x2 + 1][y1] -= c;b[x1][y2 + 1] -= c;b[x2 + 1][y2 + 1] += c;
}int main()
{cin >> n >> m >> q;for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j){scanf("%d", &a[i][j]);insert(i, j, i, j, a[i][j]);}while(q--){cin >> 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){printf("%d ", b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1]);}printf("\n");   }
}