前缀和与差分总结 - HDOJ 1556

学习链接1
学习链接2
学习链接3
学习链接4
学习链接5

再来说说自己的理解
先来写几个式子，再做定义

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;
}