C++ 實作資料結構

本篇文章撰寫中 請稍等內容完整後再閱讀… 🔗

Intro 🔗

此篇文章使用 C++ 來實作各種從基礎到進階的資料結構
可先閱讀這篇關於 C++ 內建基礎資料結構的 C++ STL 大全 後再回來繼續
STL 中的基礎資料結構只需學會如何應用即可，而此篇的資料結構則是要自行實作
內容一樣很多，若有編寫錯誤之處請使用右側聊天室回報給我，將盡快修改

---

實作資料結構 🔗

本篇包含以下資料結構的實作

• 前綴和 & 差分數列
• 稀疏表 Sparse Table
• 樹狀數組 BIT
• 線段樹 Segment Tree
• 樹堆 Treap
• 鏈結串列 Linked-list
• 並查集 DSU
• rope
• pbds

---

前綴和 & 差分數列 🔗

本篇開頭以此做為基礎，與其稱呼它們為資料結構，我更傾向將它們視為一種能有效的降低時間複雜度的重要預處理技巧

前綴和（Prefix Sum）可以簡單理解為 數列由前往後累加的值

建出前綴和數列 🔗

#include <bits/stdc++.h>
using namespace std;

signed main() 
{
    int n; cin >> n;
    vector<int> v(n), p(n+1);
    p[0] = 0;
    for(int i=0;i<n;++i)
    {
        cin >> v[i];
        sum[i+1] = v[i] + p[i];
    }
    for(auto i:p) cout << i << ' ';
}

注意：前綴和數列會比原數列多了一項，記得初始化第 0 項為 0

Input 🔗

5
1 2 3 4 5

Output 🔗

0 1 3 6 10 15 

快速查詢區間和 🔗

要查詢數列區間 $[l,r]$ 的和，原始方法是用迴圈慢慢加

int sum = 0;
for(int i=l;i<=r;++i) sum += p[i];

有了前綴和後，每次查詢使用一次減法 第 r+1 項 - 第 l 項 即可快速取得區間和，直接將時間複雜度從 $O(n)$ 降到 $O(1)$

int q,l,r; cin >> q;
while(q--)
{
    cin >> l >> r;
    cout << p[r+1] - p[l] << '\n';
}

內建函數 🔗

std 內建了可以建立前綴和的函數 partial_sum(原數列起點, 原數列終點, 新數列起點)，使用方法如下：

#include <bits/stdc++.h>
using namespace std;

signed main() 
{
    int n; cin >> n;
    vector<int> v(n), p(n+1);
    for(auto &i:v) cin >> i;
    partial_sum(v.begin(), v.end(), p.begin()+1);
    for(auto i:p) cout << i << ' ';
}

前綴和能快速取得區間和，而快速取得區間的最大/最小值則會用到本篇內容之一的 稀疏表 Sparse Table

補充：後綴和（Suffix Sum）
會前綴和就知道後綴和就是由後往前累加的值，可以自己試著建看看

二維前綴和 🔗

二維前綴和是前綴和概念在二維空間的擴展，可快速查詢二維平面上任意子矩形的數值總和

首先要先了解排容原理

$A \cup B = A + B - A \cap B$

而二維前綴和也運用了這個原理

建出二維前綴和 🔗

#include <bits/stdc++.h>
#define RPT(i,n) for(int i=1;i<=n;++i)
using namespace std;

const int N = 100;
int tb[N][N], pre[N][N];

signed main() 
{
    int r,c; cin >> r >> c;
    RPT(i,r) RPT(j,c)
    {
        cin >> tb[i][j];
        pre[i][j] = pre[i-1][j] + pre[i][j-1] 
                  - pre[i-1][j-1] + tb[i][j];
    }
    RPT(i,r) RPT(j,c) cout << pre[i][j] << " \n"[j == c];
}

Input 🔗

3 3
1 2 3
4 5 6
7 8 9

Output 🔗

1 3 6
5 12 21
12 27 45

查詢子矩形總和 🔗

建完二維前綴和後每個子矩形皆會在右下角的點形成總和
查詢任意子矩形都可以用排容原理計算出來
不用使用雙重迴圈一個一個加起來
以下示範計算 (x1,y1) 到 (x2,y2) 的子矩形總和

int q; cin >> q;
while(q--)
{
    int x1,x2,y1,y2;
    cin >> x1 >> y1 >> x2 >> y2;
    x1--; y1--;
    int sum = pre[x2][y2] - pre[x1][y2] 
            - pre[x2][y1] + pre[x1][y1];
    cout << ans << '\n';
}

差分數列 🔗

與前綴和相反的概念，差分數列為原數列相鄰元素的差值

建出差分數列 🔗

#include <bits/stdc++.h>
using namespace std;

signed main() 
{
    int n; cin >> n;
    vector<int> v(n), d(n);
    cin >> v[0]; d[0] = v[0];
    for(int i=1;i<n;++i)
    {
        cin >> v[i];
        d[i] = v[i] - v[i-1];
    }
    for(auto i:d) cout << i << ' ';
}

我們要解決以下問題：

在區間 [l,r] 加上 x，經過多次不同的操作後，求最後的數列

有了差分數列我們就不用每次操作都用迴圈在原數列上從 l 到 r 逐個加上 x
只需在差分數列上做以下兩步操作：

1. 第 l 項 + x（相當於將原數列第 l 項開始以後的數都 + x）
2. 第 r+1 項 - x（相當於將原數列第 r+1 項開始以後的數停止 + x）

所以不管區間 [l,r] 多大，都只用兩次加減法操作就能達成在區間 [l,r] 加上 x
所有操作結束後對差分數列做一次前綴和即可得到最後的數列結果，也成功降低了時間複雜度

int q,l,r,x; cin >> q;
while(q--)
{
    cin >> l >> r >> x;
    d[l] += x;
    d[r+1] -= x;
}
int sum = 0;
for(int i=0;i<n;++i)
{
    sum += d[i];
    cout << sum << ' ';
}

注意：此方法只適用於不需要中途詢問的情況，前綴和 & 差分如果要帶修改則會用到本篇內容之一的 BIT 樹狀數組

補充：二維差分數列
可以自行試著建看看，能有效地處理二維矩形區域更新的操作

小結 🔗

這兩種資料結構在處理區間操作時非常有用，特別是在需要頻繁進行區間求和或區間更新的問題中

差分和前綴和互為逆運算
對差分數列做前綴和 或 對前綴和數列作差分 都會獲得 原陣列

---

稀疏表 Sparse Table 🔗

---

樹狀數組 BIT 🔗

樹狀樹組，英文叫做 Fenwick Tree 或 Binary Indexed Tree，又簡稱 BIT，由 Fenwick 在
1994 年提出，用來解決「動態前綴和」問題

---

線段樹 Segment Tree 🔗

---

樹堆 Treap 🔗

---

鏈結串列 Linked-list 🔗

---

並查集 DSU 🔗

Disjoint Set Union-find

---

rope 🔗

rope 是一個很強大的字串處理資料結構，聽說是為了與字串 string（英譯：細繩）做對比才叫做 rope（英譯：粗繩）的，其底層是一棵持久化平衡樹，因此在做合併或在中間插入的期望時間複雜度是 $O(\log n)$

---

pbds 🔗

---

點擊回到導覽頁面 🔗

---