總結-資料結構

資料結構

1. 樹狀數組

• 寫起來很友善, 用的比較多, 比線段樹更實用吧. 雖然原理到現在不太清楚...
• 往往沒有裸樹狀數組的題目, 往往和其他算法相結合.
• 單次修改或查詢: O(logn)

• 1. BZOJ-2716-天使玩偶angel-CDQ分治 cdq分治
• 2. BZOJ-1878-HH的項鍊-SDOI2009 離線處理, 求種數
• 3. BZOJ-3289-Mato的檔案管理-莫隊+樹狀數組 莫隊, 用樹狀數組統計逆序對
• 4. CODEVS-1082-線段樹練習3-splay 比較新的思路

• 樹狀數組的弱點是不支援區間最大最小值什麼的, 但是利用它可以統計字首和的性質可以進行離線處理或統計某一時刻的資料. 還有可以通過轉化的方式使它支援相減. 比如不根據位置而根據權值統計、維護權值出現次數等等.

2. 線段樹

• 線段樹操作比較齊全, 區間或單點修改、求和、求最大最小值, 支援一些标記比如增加、乘法等. 但是除非資料特殊不支援區間翻轉.
• 因為統計功能比較強大, 是以有很多變種. 比如和樹鍊剖分結合, 以及zkw線段樹、函數式線段樹(主席樹).
• 有時需要動态開點
• 單次修改或查詢: O(logn)

• 1. CODEVS-2018-反病毒軟體-線段樹 求第二大
• 2. BZOJ-3110-K大數查詢-ZJOI2013-整體二分 打标記删除整棵樹
• 3. COGS-930-找第k小的數-HNOI2012-主席樹 函數式線段樹
• 4. BZOJ-2588-Count-on-a-tree-SPOJ10628-LCA+主席樹 函數式線段樹
• 5. BZOJ-3531-旅行 動态開點線段樹, 和鍊剖結合. 建立多棵線段樹
• 6. BZOJ-1036-樹的統計Count 鍊剖
• 7. CODEVS-1082-線段樹練習3-splay 經典應用

3. splay

• splay支援的操作是這幾項裡最全的, 除了上面的還有區間插入、移動等.
• 可以自底向上, 可以自頂向下, 效率前者高一些, 但有的題目不能做.
• 上面各種資料結構的題其實都可以用splay做, 不過splay常數略大吧.
• splay的巅峰之作就是維護數列了吧. 标記下傳真的太頭疼了.
• 單次修改或查詢: O(logn). 常數比較大.

• 1. [codevs 1343] 蚱蜢(省隊選拔賽湖南) 自頂向下. 維護區間最大值, 支援單點移動.
• 2. [codevs 1514] 書架 隻能采用自底向上的splay. 因為不是已知位置而是已知編号.
• 3. [codevs 1743] 反轉卡片 區間翻轉
• 4. CODEVS-1758-維護數列-NOI2005-splay 各種操作, 标記下傳和維護難度很大, 要求統計最大和子序列.
• 5. CODEVS-3303-翻轉區間 同上
• 6. CH-Round-#63-OrzCC杯#2省選熱身賽 平衡樹優化動态規劃
• 7. CODEVS-1082-線段樹練習3-splay 常數大的缺點暴露了

4. 并查集

• 成本效益很高的算法. 支援集合合并和查找, 以及求秩
• 單次合并或查找: O(1)

• 1. [BZOJ 1012] 最大數maxnumber 更友善地維護單調棧
• 2. BZOJ-2001-city城市建設-HNOI2010-CDQ分治 cdq分治, 多次求解最小生成樹.
• 3. CODEVS-1074-食物鍊-并查集 權值并查集, 比較好的題目.

5. 哈希表

• 主要用于判重, 做的題少(平常都用STL的set或者map了)
• 單次查找: O(1)
• 1. BZOJ-2761-不重複數字 裸hash, 模的數并不是越大越好(還要清零)

總結一下就是序列操作類的題目還可以做, 但遇到其他的比如字元串就隻能STL暴力了.