系列索引：

• NOIp 數據結構專題總結 (1)
• NOIp 數據結構專題總結 (2)

STL structure

std::vector

#include <vector> std::vector<type> v; v.push_back(x); v.pop_back(); int *a = new int[N];

std::bitset

#include <bitset> std::bitset<size> bs;

神似 bool 數組。

SAO操作：

std::bitset<N> g[N]; // store a graph, O(n^2/32)

std::map

#include <map> std::map<typeA, typeB> mp; mp[x] = y;map<int,bool> g[n]; g[x][y] = true; map<int,bool>::iterator it; for (it=g[x].begin(); it!=g[x].end(); ++it)it->first, it->second

std::queue

#include <queue> std::queue<type> q; q.push(x); q.pop(); x = q.front();

std::stack

#include <stack> std::stack<type> s; s.push(x); s.pop(); x = s.top();

std::deque

#include <queue> / #include <deque> std::deque<type> dq;

std::priority_queue

#include <queue> std::priority_queue<type> pq; // default: greater first std::priority_queue<int, std::vector<int>, std::greater<int> > pq; // lower first struct type { friend bool operator < (type a, type b) {return ...;} }; struct cmp { bool operator() (type a, type b) {return ...;} }; std::priority_queue<type, std::vector<type>, cmp> pq;

std::set

#include <set> std::set<type> st; // 會自動去重 std::multiset<type> st2; // 不去重

時間復雜度每次操作 \(O(\log{n})\)。

堆 Heap

Pure

復雜度均攤 \(O(\log{n})\).

void put(int x) {int now = ++heap_size, next;heap[heap_size] = x;while (now > 1) {next = now >> 1;if (heap[now] >= heap[next]) break; // lower rootswap(heap[now], heap[next]);now = next;} }int get(int x) {int now = 1, next, res = heap[1];heap[1] = heap[heap_size--];while ((now << 1) <= heap_size) {next = now << 1;if (next < heap_size && heap[next+1] < heap[next]) next++;swap(heap[now], heap[next]);}return res; }

堆的初始化：新建一個空堆，把這些元素依次加進堆，時間 \(O(n\log{n})\)。如果把這些元素 random_shuffle 一下再加進來，期望時間 \(O(n)\)?？梢韵入S意把這些元素放進完全二叉樹，再考慮從底向上令每個子樹滿足堆性質。

堆的刪除：因為我們只關心堆頂的元素，我們可以把被刪掉的元素暫時留在堆中，并保證當前堆頂的元素未被刪除即可。一種實現方法是再開一個堆存儲被刪除但留在原堆中的元素，一旦兩個堆堆頂相等，就一起彈出堆頂?？倳r間復雜度 \(?(?\log{?})\)，這個方法也適用于 std::priority_queue。

STL <algorithm>

void put(int x) {heap[++heap_size] = x;// greater heappush_heap(heap + 1, heap + heap_size + 1);// lower heappush_heap(heap + 1, heap + heap_size + 1, greater<int>()); }int get() {// greater heappop_heap(heap + 1, heap + heap_size + 1);// lower heappop_heap(heap + 1, heap + heap_size + 1, greater<int>());return heap[heap_size--]; }

STL std::priority_queue

(refer to above)

并查集 Disjoint Set

路徑壓縮優化：查詢一個元素時，將其到根路徑上所有元素的父親更新為當前的根。時間復雜度 \(\approx O(n)\)（均攤每次 \(O(1)\)）。只用路徑壓縮優化的并查集實際上能被構造數據卡到 \(O(n\log{n})\)。

for (int i=1; i<=n; i++) fa[i]=i;int find(int x) {return fa[x]==x ? x : fa[x]=find(fa[x]); } void join(int x, int y) {x=find(x),y=find(y); fa[x]=y; }

帶權并查集：在集合的根上加一個值為 \(x\) 的標記。對于一般的帶權并查集，一個元素到根路徑上的標記之和就是這個元素的實際權值。路徑壓縮時需要注意路徑壓縮對標記效果的影響。

int f[], sum[];int fa(int x) {if (f[x]==x) return x;else {int r=fa(f[x]);sum[x]+=sum[f[x]];return f[x]=r;} }int main() {int n, m;while (~scanf("%d%d", &n, &m)) {for (int i=0; i<=n; ++i) fa[i]=i;for (int i=1, x, y, z; i<=m; ++i) {scanf("%d%d%d", &x, &y, &z);int fx=fa(x), fy=fa(y);if (fx!=fy) f[fy]=fx, sum[fy]=sum[x]-sum[y]+z; // 類似向量運算else if (sum[y]-sum[x]!=z) ++ans; // 發現矛盾}printf("%d\n", ans);}return 0; }

帶權并查集可參考 Link 。

按秩合并優化：“秩”即并查集維護的有根樹的深度。合并兩個集合時，可以選擇深度較小的有根樹連接到另一棵上，深度較大的有根樹深度會發生改變僅當兩樹深度相等。如果我們定義一個點的樹深度為 \(0\)，在這種合并策略下，深度為 \(i\) 的有根樹至少有 \(2^i\) 個元素，那么每次操作的時間復雜度顯然不超過 \(O(\log{n})\)，總時間復雜度 \(O(n\log{n})\)。顯然可以在按秩合并的同時采用路徑壓縮進一步優化，時間復雜度 \(O(n\cdot\alpha(n))\)。

for (int i=1; i<=n; i++) fa[i]=i;int find(int x) {return fa[x]==x ? x : fa[x]=find(fa[x]); } //有路徑壓縮void join(int x, int y) {x=find(x),y=find(y);if (rank[x] < rank[y]) fa[x]=y;else {fa[y]=x; if(rank[x]==rank[y]) ++rank[x]; } }

操作撤消：未使用任何優化時，直接將合并操作時連接的邊刪去即可。使用路徑壓縮優化后，一次合并操作連接的邊可能被壓縮掉，難以撤銷；如果只使用按秩合并優化，顯然不會影響撤銷操作。支持撤銷操作的并查集可以做到 \(O(n\log{n})\) 的總時間復雜度。

按大小合并優化：每次將較小的集合的根連接到較大的上?？紤]一個元素到根的路徑上，每經過一條邊，說明其所在集合的大小至少擴大一倍，顯然不超過 \(O(\log{n})\) 條。時間復雜度 \(O(n\log{n})\)。

ST 表 Sparse Table

Range Maximum/Minimum Query：用 \(f(k,i)\) 表示 \([i,i+2^k-1]\) 的最大值，則有 \(f(k+1,i)=\max\{f(k,i),f(k,i+2^k)\}\)（最小值同理）。查詢 \([l,r]\) 時，我們找到最小的 \(k\) 滿足 \(2^{k+1}\ge r-l+1\)，由于重復統計不影響最值，\(\max?[l,r]=\max\{f(k,l),f(k,r-2^k+1)\}\)。預處理 \(O(n\log{n})\)，每次查詢 \(O(1)\)。

inline void ST() {for (int i=1; i<=n; i++) f[i][0]=data[i];for (int j=1; (1<<j)<=n; ++j)for (int i=1; i+(1<<j)-1<=n; ++i)f[i][j] = max(f[i][j-1], f[i+(1<<j-1)][j-1]); }inline int query(int l, int r) {int k=0;for (; (1<<k)<=(r-l+1); ++k); --k;return max(f[l][k], f[r-(1<<k)+1][k]); }

求 LCA：ST 表 + DFS 序。 (refer to Graph Theory)

Hash 表

將復雜信息按其 Hash 值存儲到對應位置上。數組 + 鏈表。每次期望時間 \(O(1)\)。

自然溢出：高效，省去取模。

保證正確性：

• 模數盡量采用質數，避免被數論相關性質影響。
• 雙 Hash：用兩種不同的方式求出 Hash 值分別對比。
• 混合 Hash：乘法、加法、異或、取模。
• 隨機 Hash 中用到的常數，例如模數、乘數等，避免針對。

雜項

Huffman 樹和 Huffman 編碼：參考 Link 。

轉載于:https://www.cnblogs.com/greyqz/p/ds.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的NOIp 数据结构专题总结 (1)：STL、堆、并查集、ST表、Hash表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。