數(shù)據(jù)結(jié)構(gòu)

1. 樹狀數(shù)組

• 寫起來(lái)很方便, 用的比較多, 比線段樹更實(shí)用吧. 雖然原理到現(xiàn)在不太清楚...
• 往往沒有裸樹狀數(shù)組的題目, 往往和其他算法相結(jié)合.
• 單次修改或查詢: O(logn)

• 1. BZOJ-2716-天使玩偶angel-CDQ分治?cdq分治
• 2. BZOJ-1878-HH的項(xiàng)鏈-SDOI2009?離線處理, 求種數(shù)
• 3.?BZOJ-3289-Mato的文件管理-莫隊(duì)+樹狀數(shù)組?莫隊(duì), 用樹狀數(shù)組統(tǒng)計(jì)逆序?qū)?/span>
• 4.?CODEVS-1082-線段樹練習(xí)3-splay?比較新的思路

• 樹狀數(shù)組的弱點(diǎn)是不支持區(qū)間最大最小值什么的, 但是利用它可以統(tǒng)計(jì)前綴和的性質(zhì)可以進(jìn)行離線處理或統(tǒng)計(jì)某一時(shí)刻的數(shù)據(jù). 還有可以通過(guò)轉(zhuǎn)化的方式使它支持相減. 比如不根據(jù)位置而根據(jù)權(quán)值統(tǒng)計(jì)、維護(hù)權(quán)值出現(xiàn)次數(shù)等等.

2. 線段樹

• 線段樹操作比較齊全, 區(qū)間或單點(diǎn)修改、求和、求最大最小值, 支持一些標(biāo)記比如增加、乘法等. 但是除非數(shù)據(jù)特殊不支持區(qū)間翻轉(zhuǎn).
• 因?yàn)榻y(tǒng)計(jì)功能比較強(qiáng)大, 所以有很多變種. 比如和樹鏈剖分結(jié)合, 以及zkw線段樹、函數(shù)式線段樹(主席樹).
• 有時(shí)需要?jiǎng)討B(tài)開點(diǎn)
• 單次修改或查詢: O(logn)

• 1.?CODEVS-2018-反病毒軟件-線段樹?求第二大
• 2.?BZOJ-3110-K大數(shù)查詢-ZJOI2013-整體二分?打標(biāo)記刪除整棵樹
• 3.?COGS-930-找第k小的數(shù)-HNOI2012-主席樹?函數(shù)式線段樹
• 4.?BZOJ-2588-Count-on-a-tree-SPOJ10628-LCA+主席樹?函數(shù)式線段樹
• 5. BZOJ-3531-旅行?動(dòng)態(tài)開點(diǎn)線段樹, 和鏈剖結(jié)合. 建立多棵線段樹
• 6.?BZOJ-1036-樹的統(tǒng)計(jì)Count?鏈剖
• 7.?CODEVS-1082-線段樹練習(xí)3-splay?經(jīng)典應(yīng)用

3. splay

• splay支持的操作是這幾項(xiàng)里最全的, 除了上面的還有區(qū)間插入、移動(dòng)等.
• 可以自底向上, 可以自頂向下, 效率前者高一些, 但有的題目不能做.
• 上面各種數(shù)據(jù)結(jié)構(gòu)的題其實(shí)都可以用splay做, 不過(guò)splay常數(shù)略大吧.
• splay的巔峰之作就是維護(hù)數(shù)列了吧. 標(biāo)記下傳真的太頭疼了.
• 單次修改或查詢: O(logn). 常數(shù)比較大.

• 1.?[codevs 1343] 蚱蜢(省隊(duì)選拔賽湖南)?自頂向下. 維護(hù)區(qū)間最大值, 支持單點(diǎn)移動(dòng).
• 2.?[codevs 1514] 書架?只能采用自底向上的splay. 因?yàn)椴皇且阎恢枚且阎幪?hào).
  
• 3. [codevs 1743] 反轉(zhuǎn)卡片?區(qū)間翻轉(zhuǎn)
• 4.?CODEVS-1758-維護(hù)數(shù)列-NOI2005-splay?各種操作, 標(biāo)記下傳和維護(hù)難度很大, 要求統(tǒng)計(jì)最大和子序列.
• 5.?CODEVS-3303-翻轉(zhuǎn)區(qū)間?同上
• 6.?CH-Round-#63-OrzCC杯#2省選熱身賽?平衡樹優(yōu)化動(dòng)態(tài)規(guī)劃
• 7.?CODEVS-1082-線段樹練習(xí)3-splay?常數(shù)大的缺點(diǎn)暴露了

4. 并查集

• 性價(jià)比很高的算法. 支持集合合并和查找, 以及求秩
• 單次合并或查找: O(1)

• 1.?[BZOJ 1012] 最大數(shù)maxnumber?更方便地維護(hù)單調(diào)棧
• 2.?BZOJ-2001-city城市建設(shè)-HNOI2010-CDQ分治?cdq分治, 多次求解最小生成樹.
• 3. CODEVS-1074-食物鏈-并查集?權(quán)值并查集, 比較好的題目.

5. 哈希表

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

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

總結(jié)

以上是生活随笔為你收集整理的总结-数据结构的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。