差分 【一维差分和二维差分】

全文目录

• 🤔一维差分
• • 😕差分数组的构建
• 🤔二维差分
• • 😕差分矩阵的构建

---

🤔一维差分

首先来了解一下差分的性质，差分是前缀和的逆运算，如果说前缀和是：S = f(n) ，那么差分就是 D = f^-1(n) ，也就是说，原数组是差分数组的前缀和。

原数组：a[i]，差分数组：b[i]

差分数组满足：

a[0 ]= 0;

b[1] = a[1] - a[0];

b[2] = a[2] - a[1];

b[3] = a[3] - a[2];
...
1
2
3
4
5
6
7