一份會逾時的解法和一份能拿滿分的解法之間的差別，很少僅僅在於巧思——通常是在恰當的時機選對了恰當的資料結構。
在競賽程式設計中，你會拿到一道題、一個時間限制（通常是一到兩秒）以及緊張的記憶體預算。同樣的邏輯，會因為你的操作是在線性時間、對數時間還是常數時間內完成而決定通過與否。因此，熟練掌握一組聚焦的競賽程式設計資料結構，是學生能做的回報最高的事情之一。下面我們將逐一講解最重要的幾種結構，大致依你應當學習的順序排列，並把它們對應到各自能解鎖的題型。
從基礎打起
在伸手去拿任何花俏的工具之前，先把基本元件用熟。大多數賽題——以及絕大多數入門級題目——僅憑這些就能解決：
- 陣列與動態陣列（vector），用於按索引儲存和前綴和。
- 堆疊與佇列，用於排序、回溯和廣度優先走訪。
- 雜湊表與雜湊集合，用於近似常數時間的查找、計數和去重。
- 有序集合與有序對映（平衡二元搜尋樹），當你既需要查找又需要有序時使用。
- 優先佇列（堆積），用於始終取出下一個最小或最大的元素——它是 Dijkstra 演算法和貪婪排程的骨幹。
在 C++ 中，所有這些都隨標準範本庫（STL）一同提供，這也是 C++ 在競賽中始終流行的原因之一。把 STL 用熟，意味著你能把比賽時間花在思考問題本身，而不是重新實作一個堆積。如果你才剛剛起步，我們的競賽程式設計專案會透過有意識、有評分的練習培養這種熟練度，而不是零散地刷題。
能奪獎的那些結構
當基礎變成本能之後，一小批更進階的結構會在更難的組別中反覆出現。其中三種值得單獨點名：
並查集（Union-Find）
並查集（DSU）維護一組被劃分為若干不相交集合的元素，提供兩種操作：find（這個元素屬於哪個集合？）和 union（合併兩個集合）。配合路徑壓縮和按秩合併，兩種操作都能在近乎常數的攤還時間內完成。它是連通性問題以及 Kruskal 最小生成樹演算法的標準工具。
樹狀陣列（Fenwick Tree）
樹狀陣列由 Peter Fenwick 於 1994 年首次提出，能在 O(log n) 時間內回答前綴和查詢並完成單點更新。它佔用與原陣列相同的記憶體，且程式碼簡短，因此當一道題純粹是單點更新加區間求和時，它就是首選。
線段樹（Segment Tree）
線段樹是更通用的表親。每個節點代表陣列的一個區間，讓你能夠回答區間最小值、最大值、求和或 gcd 查詢——並且藉助懶惰傳播，可以一次性更新整個區間。它佔用的記憶體大約是樹狀陣列的四倍，程式碼也更長，所以實用的判斷法則很簡單：
當你只需要單點更新下的區間求和時，伸手去拿樹狀陣列。一旦你需要最小值、最大值、區間更新，或任何樹狀陣列無法求逆的操作，就立刻換成線段樹。
這如何對應到真實賽事
美國計算機奧林匹亞競賽（USACO）把這種進階過程展現得淋漓盡致。它在一年中舉辦數場線上比賽，每場三道題、滿分 1000 分，學生依次晉升四個組別：Bronze、Silver、Gold 和 Platinum。
- Bronze 獎勵完全搜尋、排序、貪婪和基礎資料結構。
- Silver 倚重圖與樹，外加堆疊和佇列。
- Gold 引入滑動視窗以及單點更新區間求和問題——正是樹狀陣列和線段樹發揮價值的地方。
- Platinum 要求精通區間查詢、掌握進階的樹技巧，並能創造性地組合上述各種結構。
這道階梯令人鼓舞：你不必在第一天就掌握每一種結構。每個組別只要求一兩件新工具，所以穩紮穩打的學習者可以一路攀登而不至於精疲力竭。在我們的賽事總覽上瀏覽往年題目，是了解每個難度等級期待哪種結構的好方法。
一份實用的學習順序
- 把陣列、前綴和以及 STL 容器用熟。
- 加上堆疊、佇列、堆積和雜湊表，直到它們成為本能。
- 學習並查集，然後是樹狀陣列，再然後是線段樹。
- 在經典題集上練習，並覆盤每一道你沒能做完的題。
持續且經過覆盤的練習，每一次都勝過單純堆量。如果你想要一條從 STL 基礎到奪獎級區間查詢的結構化路徑——並得到經驗豐富的教練的回饋——歡迎了解 BIAA 的競賽程式設計方向，開始打造那套能把難題變成已解之題的工具箱。