前缀和与差分总结 - HDOJ 1556
再来说说自己的理解
先来写几个式子，再做定义
A[0] = B[0] A[1] = B[0] + B[1] A[2] = B[0] + B[1] + B[2] A[3] = B[0] + B[1] + B[2] + B[3] ... A[n] = B[0] + B[1] + B[2] + ... + B[n]
根据以上式子，可以推导得：
B[0] = A[0] B[k] = A[k] - A[k - 1]
定义：A 数组是 B 数组的前缀和，B 数组是 A 数组的差分
由于这两个数组都是一维的，所以也可以叫做一维前缀和和一维差分
Q1：前缀和有什么作用？
A：求 B 数组任意区间 [l, r] 的和
S = B[l] + B[l + 1] + ... + B[r] A[r] = B[0] + B[1] + ... + B[l - 1] + B[l] + ... + B[r] A[l - 1] = B[0] + B[1] + ... + B[l - 1] S = A[r] - A[l - 1]
所以，求 B 数组的和的问题，原本是 O(n) 的，利用 B 数组的前缀和 A 数组，就转化为了 O(1) 时间
Q2：差分数组有什么作用？
A：让 A 数组任意区间 [l, r] 每个数都加上常数 c
A[l] += c, A[l + 1] += c, ..., A[r] += c <=> B[l] += c B[r + 1] -= c
注意，B 数组是 A 数组的差分数组，B[l] 的变化，会影响到 A 数组中从 l 开始直到最后一个值的变化
A[l] = B[0] + B[1] + ... + B[l] A[l + 1] = B[0] + B[1] + ... + B[l] + B[l + 1] A[l + 2] = B[0] + B[1] + ... + B[l] + B[l + 1] + B[l + 2]
所以，B[l] 的变化导致了所有的变化，B[r+1] 的变化是还原操作
Q3：怎么理解？
A：前缀 <=> 积分 && 差分 <=> 求导
不是特别像，但是可以从中体会到这个感觉
一维差分 <=> 一维求导，y = ax + b 求导一次，常数不见，得到系数
二维差分见上面链接，思维类似
模板题：HDOJ1556
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 20;
int n;
int a, b;
int sum[maxn], diff[maxn];
int main(){
//freopen("input.txt", "r", stdin);
while(scanf("%d", &n), n){
memset(sum, 0, sizeof(sum));
memset(diff, 0, sizeof(diff));
for(int k = 1; k <= n; k++){
scanf("%d%d", &a, &b);
diff[a]++;
diff[b + 1]--;
}
for(int i = 1; i <= n; i++)
sum[i] = sum[i - 1] + diff[i];
for(int i = 1; i <= n; i++)
printf("%d%c", sum[i], i==n?'\n':' ');
}
return 0;
}