【C++】競程筆記（前綴和、差分）

程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。

前綴和（Prefix-sum）

要快速計算某區間的和，會用到前綴和。

Image Source：https://osgoodgunawan.medium.com/prefix-sum-80d531154b95

依照上圖，A 為原始序列，P 為前綴和序列，則前綴和用程式寫就是：

完整一點：

vector<int> P(n + 1, 0); // P[0] = 0
for (int i = 0; i < n; ++i) {
    P[i + 1] = P[i] + A[i];
}

我們可以利用前綴和計算區間 $[L, R]$ 的總和，可於 $O(1)$ 時間內完成，但在準備前綴和序列的時間複雜度是 $O(n)$ 。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> nums = {2, 4, 5, 7, 1, 3}; // 原始序列
    int n = nums.size();

    // 建立前綴和序列
    vector<int> prefix(n + 1, 0); // prefix[0] = 0
    for (int i = 0; i < n; ++i) {
        prefix[i + 1] = prefix[i] + nums[i];
    }

    int L = 1, R = 4; // 計算區間 [L, R] 的總和
    int rangeSum = prefix[R + 1] - prefix[L];
    
    cout << "區間 [" << L << ", " << R << "] 的總和是：" << rangeSum << endl;

    return 0;
}

輸出：

1	區間 [1, 4] 的總和是：17

例題 1

例題：https://cses.fi/problemset/task/1643

講到 Maximum Subarray Problem（最大子陣列問題），就要講到 Kadane’s Algorithm。

Kadane’s Algorithm 是專門用來找出一維數字陣列中總和最大的連續子陣列的演算法，日後在解決 DP（Dynamic Programming）上的題目會常用到這個。

:::success
子陣列（subarray）：是指一個陣列中由連續元素所構成的區間。區間可從原陣列中的任意起點開始，也可從任意位置結束。

如：int arr[] = {1,2,3,4}; 為原始陣列，則其 subarray 可為：

長度為 1 的：{1}, {2}, {3}, {4}
長度為 2 的：{1, 2}, {2, 3}, {3, 4}
長度為 3 的：{1, 2, 3}, {2, 3, 4}
長度為 4 的：{1, 2, 3, 4}

若不連續的組合如：{1, 3}、{2, 4} 就稱為子序列（subsequence）
:::

而 Kadane’s Algorithm 的演算流程如下：

通常有兩個變數：

currentSum：目前子陣列總和。
maxSum：目前找到的最大子陣列總和。

以上初始值都設為陣列中的第一個元素（即 index = 0）。

遍歷陣列：

從第二個元素開始，而每次走到一個位置的時候，都要問自己是要繼續前面的總和還是在這裡重來？計算方式如：

1	currentSum = max(現在的元素, currentSum + 現在的元素);

現在的元素從第二個元素（假設 arr[1]）開始，假設 arr[1] = 3、arr[0] = -1、currentSum = arr[0]，那經過 max 之後，他就會繼續前面的總和，變成 currentSum = 3。

更新最大總和：

如果 currentSum 比 maxSum 還大，就更新 maxSum：

1	maxSum = max(maxSum, currentSum);

延續上面的例子，確實 currentSum 比較大，就直接更新。

最後整個迴圈遍歷完後，就可以得到最大子陣列總和了。

回到最開始的例題，於是我們可以用這個演算法去做這題了：

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    long long max_sum = arr[0];
    long long current_sum = arr[0];

    for (int i = 1; i < n; ++i) {
        current_sum = max(arr[i], current_sum + arr[i]);
        max_sum = max(max_sum, current_sum);
    }

    cout << max_sum << "\n";
    return 0;
}

那你說這跟前綴和有啥屁關係？其實也是可以用前綴和解，只是要將問題稍微轉個角度想：要找出兩個位置 i < j，使得 prefix[j] - prefix[i] 最大。

以下的程式碼中，ans = max(ans, s - mn); 的 s - mn 就是 prefix[j] - prefix[i]。

// from NTUCPC Guide
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
int main() {
    int n;
    cin >> n;
 
    ll s = 0;
    ll mn = 0;
    ll ans = -LLONG_MAX;
    for (int i = 1; i <= n; i++) {
        ll x;
        cin >> x;
        s += x;
        ans = max(ans, s - mn);
        mn = min(mn, s);
    }
    cout << ans << "\n";
}

二維前綴和（2D-Prefix Sum）

給定一個大小為 m × n 的二維陣列（矩陣）A，並建立一個矩陣 P，使 P[i][j] 代表從 (0,0) 到 (i,j) 的子矩陣內所有元素的總和。

公式：

$$P[i][j]=A[i][j]+P[i−1][j]+P[i][j−1]−P[i−1][j−1]$$

要查詢任意一個矩形區域的總和時（如從 (x1, y1) 到 (x2, y2)），只需透過簡單的四個查詢值即可：

$$Sum(x1,y1,x2,y2)=P[x2][y2]−P[x1−1][y2]−P[x2][y1−1]+P[x1−1][y1−1]$$

那這樣可以先用 $O(n^{2})$ 時間算出 2D 前綴和，用 $O(1)$ 就可以求出矩形區域的和了。

來舉例一下（Python Code，因為 C++ 陣列寫起來比較麻煩）：

假設有 3x3 矩陣：

1
2
3

A = [ [1, 2, 3],
      [4, 5, 6],
      [7, 8, 9] ]

要建立一個 2D 前綴矩陣：

1
2
3

P = [ [1,  3,  6],
      [5, 12, 21],
      [12,27, 45] ]

以下是 A 的矩陣示意圖：

矩形圖_1

前綴和矩陣的 P[0][0] = 1 沒毛病，再來講講 P[1][1] = 12，其實他就是 A 裡面的 1, 2, 4, 5 做相加得出的結果，也就是以下那四塊矩形的面積（位置從矩陣 A (0, 0) 到 (1, 1)）。

矩形圖_2

以此類推，P[2][1] = 27 就是從原始矩陣 A 的位置 (0, 0) 到 (2, 1) 對 A 的 1, 2, 4, 5, 7, 8 等數字做相加，如下圖紅色區塊所示：

矩陣圖_3

接下來若要求取某段區間內的矩形範圍總和，則如下所示：

若我們不是要從 (0, 0) 出發，而是從 (1, 1) 出發，到 (2, 2) 結束呢？（某段區間求和）則用到上方的 Sum 公式：

$$Sum=P[2][2]−P[0][2]−P[2][0]+P[0][0]=45−6−12+1=28$$

畫圖的方式就如下所示：

矩陣圖_4

我們要求得右下角四塊矩形面積（在 A 矩陣中就是 5, 6, 8, 9），就會做如上圖的運算，由於因為面積為 1 的矩形被扣掉兩次，所以要給他補一次回來。

例題 2

例題（Zerojudge）a694. 吞食天地二：https://zerojudge.tw/ShowProblem?problemid=a694

#include <iostream>
#include <vector>

using namespace std;

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

    int n, m;
    while (cin >> n >> m) {
        vector<vector<int>> grid(n + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                cin >> grid[i][j];
            }
        }

        vector<vector<int>> p(n + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + grid[i][j];
            }
        }

        for (int i = 0; i < m; ++i) {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            int sum = p[x2][y2] - p[x1 - 1][y2] - p[x2][y1 - 1] + p[x1 - 1][y1 - 1];
            cout << sum << "\n";
        }
    }
    return 0;
}

基本上就是套上面給的公式：

$$P[i][j]=A[i][j]+P[i−1][j]+P[i][j−1]−P[i−1][j−1]$$

$$Sum(x1,y1,x2,y2)=P[x2][y2]−P[x1−1][y2]−P[x2][y1−1]+P[x1−1][y1−1]$$

然後稍微注意一下輸出輸入優化，並且注意輸入前綴和的部分，for 迴圈初始值是 int i = 1。

差分（Difference）

簡單來說就是陣列中相鄰兩項元素的差值。

給定一個數列 A[1...n]，我們可以定義它的差分陣列 D[1...n] 為：

$$D[i]=A[i]−A[i−1]$$ （ $A[0] = 0$ 或依照情況定義）

若知道所有的差，也就是差分陣列 D 的每一項，就可以透過相加差分陣列的第 i 項去求得原始陣列 A 的第 i 項：

$$A[i]=D[1]+D[2]+\cdots+D[i]$$

而這其實就是在做「前綴和」，因為差分是「變化量」，只要把變化量一項項累加回去，就可以得到原來的數列。

該公式可用 sigma 代號直接簡化：

$$A[i] = \sum_{k=1}^{i}D[k]$$

那差分是拿來幹嘛的呢？是拿來做快速區間加法用的。

當我們想對某個區間 $[l, r]$ 都加上一個值 $x$ 時，如果直接修改每一個 $A[i]$ ，時間複雜度是 $O(r - l + 1)$ 。

若用差分陣列，僅需做到以下操作即可：

1 2	D[l] += x D[r+1] -= x

做完以上操作後，對 D 做前綴和（還原陣列 A），就會發現 $[l, r]$ 區間都被加了 $x$ ，其餘區間不變。

以下是個 C++ 差分範例：

#include <iostream>
#include <vector>

using namespace std;

// 建立差分陣列
void difference_array(const vector<int>& A, vector<int>& D) {
    int n = A.size();
    D[0] = A[0];
    for (int i = 1; i < n; ++i) {
        D[i] = A[i] - A[i - 1];
    }
}

// 區間加值：對 [l, r] 區間加上 val
void range_add(vector<int>& D, int l, int r, int val) {
    D[l] += val;
    if (r + 1 < D.size()) {
        D[r + 1] -= val;
    }
}

// 還原原始陣列 A（前綴和）
void restore_array(const vector<int>& D, vector<int>& A) {
    int n = D.size();
    A[0] = D[0];
    for (int i = 1; i < n; ++i) {
        A[i] = A[i - 1] + D[i];
    }
}

int main() {
    // 建立原始陣列
    vector<int> A = {0, 0, 0, 0, 0};
    int n = A.size();

    // 建立差分陣列
    vector<int> D(n);
    difference_array(A, D);

    // 區間更新操作
    range_add(D, 1, 3, 5); // 對第 2~4 項加上 5
    range_add(D, 2, 4, 2); // 對第 3~5 項加上 2

    // 還原陣列
    restore_array(D, A);

    cout << "A : ";
    for (int i = 0; i < n; ++i) {
        cout << A[i] << " ";
    }
    cout << "\n";

    return 0;
}

輸出結果：

1	A : 0 5 7 7 2

例題 3

例題（Zerojudge e340. 差分練習）：https://zerojudge.tw/ShowProblem?problemid=e340

這題很簡單，只要求差分陣列即可。

B 為原始陣列，A 為差分陣列。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    
    vector<long long> B(N);
    for (int i = 0; i < N; i++) {
        cin >> B[i];
    }
    
    vector<long long> A(N);
    A[0] = B[0];
    for (int i = 1; i < N; i++) {
        A[i] = B[i] - B[i-1];
    }
    
    for (int i = 0; i < N; i++) {
        cout << A[i] << " ";
    }
    
    return 0;
}

例題 4

2021 年 11 月 APCS 第三題。

例題（Zerojudge g597. 3. 生產線）：https://zerojudge.tw/ShowProblem?problemid=g597

這題結合的演算法蠻多的，貪心法、前綴和、差分、排序都有。

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m; 
    
    // 差分用於計算每個位置的工作量
    vector<long long> diff(n, 0);
    for (int i = 0; i < m; i++) {
        int l, r, w;
        cin >> l >> r >> w;
        l--; r--; // 因為題目數字範圍關係, 為了要符合 C++ 索引規範把它 - 1
        // 以下部分是差分的區間加值運算
        diff[l] += w;
        if (r + 1 < n) diff[r + 1] -= w;
    }
    
    // 前綴和用於計算每個位置的總工作量
    // 這邊就是如同本文中提到的還原陣列的操作, 也是前綴和的操作
    vector<long long> sum_w(n, 0);
    sum_w[0] = diff[0];
    for (int j = 1; j < n; j++) {
        sum_w[j] = sum_w[j - 1] + diff[j];
    }
    
    vector<long long> t(n);
    for (int i = 0; i < n; i++) {
        cin >> t[i];
    }
    
    // 排序工作量（由大到小排序）
    sort(sum_w.rbegin(), sum_w.rend());
    // 用反向迭代器, 就只是加個 r, 就可以達成降序的效果
    
    sort(t.begin(), t.end());
    
    long long total = 0;
    for (int i = 0; i < n; i++) {
        total += t[i] * sum_w[i]; // 計算最小時間花費總和
        
    }
    
    cout << total;
    
    return 0;
}

總結

一、前綴和（Prefix Sum）

概念：

前綴和是一種預處理技巧，可於 $O(1)$ 時間內查詢任意區間 $[L, R]$ 的和。

一維前綴和：

1
2
3

vector<int> P(n + 1, 0);
for (int i = 0; i < n; ++i)
    P[i + 1] = P[i] + A[i];

查詢任意區間 $[L, R]$ 的和

1	sum = P[R + 1] - P[L];

二、二維前綴和（2D Prefix Sum）

概念：

用於矩陣中的子區域總和的查詢。

預處理公式：

$$P[i][j]=A[i][j]+P[i−1][j]+P[i][j−1]−P[i−1][j−1]$$

查詢子矩陣 $(x1, y1)$ 到 $(x2, y2)$ 總和公式：

$$Sum=P[x2][y2]−P[x1−1][y2]−P[x2][y1−1]+P[x1−1][y1−1]$$

三、差分（Difference）

概念：

差分是相鄰元素的變化量，可做快速區間加值，之後再還原成原始陣列。

差分公式：

$$D[i]=A[i]−Ai−1$$

快速區間加值：

1 2	D[l] += x; D[r + 1] -= x;

對差分陣列做前綴和即可還原 A。

比較表

演算法	功能	預處理複雜度	查詢複雜度	應用
前綴和	快速查詢區間總和	$O(n)$	$O(1)$	陣列區間查詢、DP 優化
二維前綴和	快速查詢矩形區域總和	$O(n^{2})$	$O(1)$	影像處理、即時地圖
差分陣列	快速區間加法	$O(n)$	$O(1)$（還原陣列為 $O(n)$）	線段更新