二阶差分学习笔记

前言

在不要求实时更新数组的情况下，差分是非常有用思想。相较于一阶差分的区间加，二阶差分可以进行更复杂的操作，比如将一个区间加上等差数列，或是一次性对多个特殊区间进行区间加操作。

二阶差分是一阶差分的扩展，相应的，还有更高阶数的差分，可以用来区间加多项式

前置知识

一阶差分

一阶差分可以 O(1) 实现区间加操作，最后 O(n) 求出原数组。如要求 al…ar 都加 v，则diff[l]+=v, diff[r+1]-=v即可。

同理，在二维的情况下也可以 O(1) 实现矩形区域加，最后 O(nm) 求出原数组。具体来说若 [x1, x2] × [y1, y2] 的二维区域都加 v，则diff[x1][y1]+=v, diff[x2+1][y1]-=v, diff[x1][y2+1]-=v, diff[x_2+1][y_2+1]+=v即可。

二阶差分

若每次操作要将 [l + xd1, r + xd2] 这样的一堆区间每个区间都加 v，一阶差分每次操作时间复杂度 O(x)。对于这样的问题，二阶差分可以优化为 O(k + n)，k 为操作次数。

我们先考虑一个简单的情况，若让 [3, 7]，[4, 8]，[5, 9] 区间 +1，一阶差分需要对 3 个区间分别修改diff[3]+=1, diff[8]-=1 diff[4]+=1, diff[9]-=1 diff[5]+=1, diff[10]-=1

观察到对 diff 数组的操作是 [3, 5] + 1, [8, 10] − 1，诶诶，是不是很熟悉，这不正是区间加操作吗，于是我们自然的想到开一个 diff2 数组去维护 diff 数组，这也就是二阶差分。

刚才的操作就变成了diff2[3]+=1, diff2[6]-=1 diff2[8]+=1, diff2[11]-=1，也就将 O(x) 变成了 O(1) 的复杂度。然后就简单了，先由 diff2 数组来求 diff 数组，然后再由 diff 数组求原数组即可。

这也就要求了操作对 diff 数组的影响要有一定规律，才可以用二阶差分来优化。

一些应用

区间加等差数列

定义一次操作：在 [l, r] 的区间上加一个首项 b0 公差 d 的等差数列

比如： a = [1, 2, 3, 4, 5, 6]

操作：在 [2, 5] 加上等差数列[3, 5, 7, 9]

则 a = [1, 2, 6, 9, 12, 15]

方法1：

加等差数列相当于进行多个区间加操作，区间左端点每次右移 1，右端点右移 0。加等差数列的本质是 a[l, r] + b0， diff[l + 1, r] + d，diffr + 1 − d(r − l)，可以发现，是对 a 和 diff 的区间加且对 diff 单点加。

我们用二阶差分数组 diff2 维护 diff 数组的区间加，用 diff 维护 a 的区间加即可。

MYCODE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve(){
    int n, q;
    cin >> n >> q;  
    vector<ll> diff(n + 2), diff2(n + 2);
    while(q--){
        ll l, r, x, y;
        cin >> l >> r >> x >> y;
        ll d = (y - x) / (r - l);
        diff[l] += x; diff[r+1] -= x + d * (r - l);
        diff2[l+1] += d, diff2[r+1] -= d;
    }

    for(int i=1; i<=n; i++){
        diff2[i] += diff2[i-1];
        diff[i] += diff2[i];
    }

    vector<ll> ans(n + 1);
    for(int i=1; i<=n; i++){
        ans[i] += ans[i-1] + diff[i];
    }

    ll mx = 0, x = 0;
    for(int i=1; i<=n; i++){
        x ^= ans[i];
        mx = max(mx, ans[i]);
        // cout << ans[i] << " \n"[i == n];
    }
    cout << x << ' ' << mx << '\n';

}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1; //cin >> t;
    while(t--) solve();
    
    return 0;
}

方法2：

我们还可以拆开式子，对两个部分直接用两个一阶差分进行维护

  • 区间加等差数列也就是 ax + b0 + d(x − l) (l ≤ x ≤ r)

  • 有常数项 b0 和公差 d，我们考虑用两个数组 dc, dd 来维护这两部分

  • 常数项很好维护, 直接维护差分

    dc[l] += b0, dc[r+1] -= b0

  • 考虑公差部分，化简可得 d(x − l) = dx − dl 。−dl 是一个常数，可直接更新到 dc，剩下就只有 dx，我们再用一个数组 dd 维护就好。

    所以每次操作我们就可以让:

    dc[l] -= dl, dc[r+1] += dl

    dd[l] += d, dd[r+1] -= d -> 用来表示 [l, r] 的范围内有公差 d

  • 最后对 dc, dd 求前缀和，即：

    dc[i] += dc[i-1], dd[i] += dd[i-1]

  • 这样 dc, dd 就可以表述出 ai

    a[i] = a[i] + dc[i] + i*dd[i]

每次操作 O(1)，O(n) 恢复原序列，总时间复杂度 O(k + n)。

MYCODE
1
2
3
4
5
6
7
8
9
10
11
12
13
// 在 [l, r] 上加一个首项为 lo, 公差为 d 的等差数列
dc[l] += lo - l * d;
dc[r+1] -= lo - l * d;
dd[l] += d;
dd[r+1] -= d;

for(int i=1; i<=n; i++){
    dc[i] += dc[i-1]
    dd[i] += dd[i-1]
} 
for(int i=1; i<=n; i++){
    a[i] = a[i] + dc[i] + i * dd[i]
}

题目链接 : 洛谷 P4231

区间加等差数列&实时查询

给定两个操作

  • 操作1：区间加等差数列

  • 操作2：查询 ai 的值

也就是说，我们不能每次查的时候都来一遍前缀和，这样的时间复杂度是 O(kn)。

重新思考加等差数列的过程，发现每次操作 1 本质上是对两个数组的区间加，自然的，我们可以结合线段树，这样就支持了数组的实时查询，时间复杂度 O(klogn)

题目链接 : 洛谷 P1438

Fujian CCPC 2025 INV. - B

思路：枚举 + 优化 + 优化 + 优化 &注意力惊人

对于四种牌子金银铜铁 [a1, a2, a3, a3] 有两个限制：

数量得分 求一共有 i 个奖牌时的情况数

 

4 个变量看似不可 o(n) 枚举，但我们先枚举，之后尝试优化

 

发现铜铁互相转化不会影响得分，所以可以只枚举 a1, a2，

则得分 s = 4a1 + 3a2 + (n − 8a1 − 4a2) = n − 4a1 − a2

 

只看牌子数量，铜铁互相转换，牌子数量上下界可计算

，，

 

然后对于 a1，a2 已知的情况

结合这两个限制可以很容易找出贡献区间 [l, r] (若有)，然后我们让此区间 +1，也就是牌子数量在 [l, r] 的情况数 +1

时间复杂度O(n2)，不足以通过此题

 

我们通过观察式子或打表，可以发现

对于固定的 a1

我们进行的操作会是：

[l，r] + 1，[l + 1，r + 3] + 1，[l + 2，r + 6] + 1…

也就是 l 每次右移 1，r 每次右移 3

 

于是，我们就可以使用二阶差分进行优化。建立两个二阶差分数组，分别维护左右

Ldiff2[st]++, Ldiff2[ed]++，Rdiff2[st+1]--, Rdiff2[ed+1 + 3]++

TRICK : 对于右侧，求前缀和时可以是 Rdiff2[i] += Rdiff2[i-3]，这样就实现了每次右移 3 的效果

对于每个 a1，我们只需要找到 l，r 的开始结束位置，这个可以 O(1) 找到，然后利用二阶差分，O(1) 进行区间加操作，最后前缀和还原。总时间复杂度 O(n)

MYCODE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve(){
    int n, k;
    cin >> n >> k;

    vector<ll> diff(n + 2), Ldiff2(n + 2), Rdiff2(n + 1 + 4); 
    for(int i=0; i<=n/8; i++){
        // 0 <= l <= r && 分数 >= p
        int mi = min({(n + 1)/ 2 - 3 * i, (n - (n+1)/2 - 4*i) / 2, n-k-4*i});
        if(mi >= 0){
            int j = mi;
            int l1 = (n+1)/2 - 3*i - mi;
            int r1 = n - 7*i - 3*mi;
            int l2 = (n+1)/2 - 3*i;
            int r2 = n - 7*i;
            Ldiff2[l1]++, Ldiff2[l2+1]--;
            Rdiff2[r1+1]--, Rdiff2[r2+1 + 3]++;
        }
    }

    // 还原 diff
    for(int i=1; i<=n; i++){
        Ldiff2[i] += Ldiff2[i-1];
        if(i-3>=0) Rdiff2[i] += Rdiff2[i-3];
    }
    for(int i=0; i<=n; i++){
        diff[i] = Ldiff2[i] + Rdiff2[i];
    }

    // 还原原数组
    for(int i=1; i<=n; i++){
        diff[i] += diff[i-1];
    }
    for(int i=1; i<=n; i++){
        cout << diff[i] << " \n"[i == n];
    }

}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t = 1; //cin >> t;
	while(t--) solve();
	
	return 0;
}

题目链接 : 2025 FJ CCPC INV.