首先可以先看一下 Wiki 上对差分的定义是数学中的一个概念，它将原函数 $f(x)$ 映射到 $f(x + a) - f(x + b)$。如果说差分是前缀和的一种相对策略，那么这样就不会陌生了。通常在对一些区间问题的求解的时候会要求使用 $O(n)$ 的复杂度去解决所有区间的答案求和还有对区间的修改的反馈，这时候就需要用到一些差分的思想来解决问题。
区间差分
可以做一道题来了解基本的差分思想，比如 https://www.luogu.com.cn/problem/P3397 这道题中对二维区间的修改往往无法通过暴力的方法去显现，那么怎么样表示这一修改的效果呢？有一个很常用的差分是对原序列某一区间内元素修改，可以转化为差分序列中该区间的头部加操作和尾部减操作，如果扩展到二维的空间就可以解决这个问题。
解决子数组问题
如果要遍历所有的子数组，那么时间复杂度是非常高的，这时候就应该想，一个区间的答案能不能由其他区间得来呢？使用差分可知两两区间之间答案的差值，那么知道前面区间的答案就可以推出下一个区间。https://acm.hdu.edu.cn/showproblem.php?pid=7055 这题中是将数组根据相同字母之间的距离分段，对每一段都可以计算出答案，而通过差分可以知道每段之间答案的差值和这个差值的计算方法，以此类推就可以得到所有子数组对答案贡献的和。
// The expression of an interval can be obtained by first traversing the right
// endpoint of the interval and then the left endpoint of the interval.
void solve() {
string s;
cin >> s;
vector<int> idx[26];
for (int i = 0; i < 26; i++) {
idx[i].push_back(0);
}
for (int i = 0; i < s.size(); i++) {
idx[s[i] - 'a'].push_back(i + 1);
}
for (int i = 0; i < 26; i++) {
idx[i].push_back(s.length() + 1);
}
long long ans = 0;
for (int i = 0; i < 26; i++) {
long long now = 0, pre = 0, dif = 0;
for (int j = 1; j < idx[i].size(); j++) {
long long len = idx[i][j] - idx[i][j - 1];
now = (now + pre * len) % 998244353;
// (ans_{i + 1} - ans_{i}) - (ans_{i} - ans_{i - 1})
dif = (dif + idx[i][j - 1] + idx[i][j]) % 998244353;
pre = (pre + dif) % 998244353;
}
ans = (ans + now) % 998244353;
}
cout << ans << endl;
}
当然这个题是有更简单的 DP 解法的，本题的 DP 解法其实也是某种意义上的差分算法，只是并没有显式的减出差分，而是直接通过前一个答案的贡献直接算出了扩大区间后的答案并加在总和上。这个解法要比之前的标程要更加的直观，其中也体现出了差分的思想。
void solve() {
string s;
cin >> s;
vector<long long> pre(26);
vector<long long> dp(s.length() + 1);
long long ans = 0;
for (int i = 1; i <= n; i++) {
int now = s[i] - 'a';
// update the answer according to the formula
dp[i] = (dp[i - 1] + 2 * pre[now] + i) % 998244353;
pre[now] = (pre[now] + i) % 998244353;
ans = (ans + dp[i]) % 998244353;
}
cout << ans << endl;
}
前缀和
前缀和的相关题目可能会更加的明显一些，用一个简单的前缀和数据结构就能够在 $O(1)$ 复杂度求出任意区间的和，可以用前缀和来简化计算，也可以维护任意的区间和信息。由于这个算法思想使用的非常的频繁，尤其是在 Codeforces 中的思维题中使用。
加速计算
对一个区域内的值进行加和运算也是一个需要消耗时间的操作，如果区间内值不变就可以用简单的前缀和进行预处理。https://www.luogu.com.cn/problem/P1719 中的每一行都可以先用前缀和处理一遍，使得 $O(n^{4})$ 转变成了 $O(n^{3})$。
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
int sum = 0;
for (int k = 1; k <= n; k++) {
// directly using the prefix sum
sum += f[j][k] - f[i - 1][k];
if (sum < 0) sum = 0;
ans = max(sum, ans);
}
}
}
维护区间信息
比如这个题目 https://leetcode-cn.com/problems/subarray-sum-equals-k/ 中的子数组的和就能够通过前缀和数组来得到，通过一个数学转换把 $Sum_{r}-Sum_{l}=k$ 转换为查询当前前缀和有没有其他前缀和满足 $Sum_{other}+k=Sum_{now}$，这样就能够用哈希表存储并查询。