前缀和算法

前缀和主要适用的场景是原始数组不会被修改的情况下，频繁查询某个区间的累加和。

前缀和核心代码

1
2
3
4
5
6
7
int nums[110],prefix[110];
int n;
cin>>n;
for(int i=1;i<=100;i++){
    cin>>nums[i];
    prefix[i] = prefix[i-1] + nums[i];
}

前缀和数组prefix[i] 就代表着 nums[0..i] 所有元素的累加和，如果我们想求区间 nums[i..j] 的累加和，只要计算 prefix[j] - prefix[i-1] 即可，而不需要遍历整个区间求和。

后缀和

后缀和和前缀和类似，只是建立数组的过程不太一样

1
2
3
4
5
6
for(int i=1;i<=n;i++){
    cin>>nums[i];
}
for(int i=n;i>=1;i--){
    sum[i] = sum[i+1] + nums[i];
}

这里的sum数组sum[i]的含义就是 nums[i..n] 的所有元素的累加和

差分数组

差分数组和前缀和思想非常类似，差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。

比如说，我给你输入一个数组 nums，然后又要求给区间 nums[2..6] 全部加 1，再给 nums[3..9] 全部减 3，再给 nums[0..4] 全部加 2，再给…
然后问你，最后 nums 数组的值是什么？

常规的思路很容易，你让我给区间 nums[i..j] 加上 val，最简单的方法就是一个 for 循环给它们都加上。这种思路的时间复杂度是 O(N)，由于这个场景下对 nums 的修改非常频繁，所以效率会很低下。

这里就需要差分数组的技巧，类似前缀和技巧构造的 prefix 数组，我们先对 nums 数组构造一个 diff 差分数组，diff[i] 就是 nums[i] 和 nums[i-1] 之差

这样构造差分数组 diff，就可以快速进行区间增减的操作，如果你想对区间 nums[i..j] 的元素全部加 3，那么只需要让 diff[i] += 3，然后再让 diff[j+1] -= 3 即可

差分数组核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int nums[110],diff[110];
//构建差分数组
for (int i = 1; i <= 100; i++) {
    cin >> numsa[i];
    diff[i] = nums[i] - nums[i-1];//差分数组
}

//给定区间的修改，修改m次
while(m--){
    cin>>l>>r;
    cin>>x;
    diff[l] += x;
    if (r + 1 <= n) { //不越界
        diff[r+1] -= x;
    }
}

//利用差分数组还原数组
for(int i=1;i<=100;i++){
    nums[i] = nums[i-1] + diff[i];
    cout<<nums[i]<<" ";
}

越界判断：
当 r+1 >= diff.length 时，说明是对 nums[i] 及以后的整个数组都进行修改，那么就不需要再给 diff 数组减 val 了。

参考