你認為最優美的數據結構是什麼？

12-30

如題。

並查集：

int find(int x) { if(x!=fa[x]) fa[x]=find(fa[x]); return fa[x]; } void union(int x,int y) { int a=find(x),b=find(y); if(a!=b) fa[b]=a; }

樹狀數組：

int a[maxn]; int lowbit(int x) { return x(-x); } void add(int x,int y) { while(x&<=n) { a[x]+=y; x+=lowbit(x); } } int sum(int x) { int s=0; while(x&>0) { s+=a[x]; x-=lowbit(x); } return s; }

實現簡單，代碼優雅，效果拔群。

前置技能：您需要確認自己知道trie是幹什麼的；

您需要確認自己會用vector或者之類的容器來實現trie。

我覺得最優美的數據結構是並查集和線段樹。然而已經被別的答主說過了，我談談幾年前看到的一個東西：哈希樹(hashTree)。

以下討論膜質數的hash方式。

hash的衝突

眾所周知，hash是有衝突的。隨著表中元素變多，衝突的概率快速增大。

（有個結論：取 $sqrt n$ 個 $[1,n]$ 中的隨機數，就期望有一個值被取了多遍。因此，元素越來越多，衝突的概率增長得相當快。）

舉個例子：假設我們的哈希函數是 $h(x) = x \% 17$ ，那麼h(19)=2，h(36)也是2。我們稱這種情況為衝突——假設我們加入了19，hash表裡面存下了19的哈希值為2。後來，面對查詢「36是否存在」的時候，hash表查到36的哈希值是2，就會毫不猶豫地回答「存在」——這樣就出錯了。

為了解決hash衝突的問題，我們一般使用兩種方法：「拉鏈法」和「跳躍法」。

拉鏈法：簡單粗暴，給每一個hash值開一個鏈表，存下真實值。空間是可保證的，具體開鏈表的方法參考鄰接表（或者，「前向星」）。

這個方法的漏洞在於：時間複雜度將無法得到保證。還是剛剛的哈希函數，我們存下19,36,53,70……這樣，時間複雜度直接被卡到 $O(n)$ 每次查詢。

那麼有沒有辦法解決上述問題呢？把鏈表改成跳錶（或者其他平衡樹，或者直接std::set），這樣時間複雜度就穩定在 $O(log n)$ .但是需要付出較大的常數。

跳躍法：又稱「線性探查法」。也是存下真實值，不同的是，我們求出hash值之後，如果發現那個hash值已經有元素了，我們就往後面跳k位……如此往複，直到出現空位為止。

這個演算法的複雜度非常不靠譜，我也沒想到解決辦法。

綜上：我們能做時間複雜度穩定在 $O(log n)$ 的hash，但是需要付出很大的常數代價。

哈希樹

哈希樹的思想是：膜多個質數。

也許您看到這麼簡單的思路，會D我：這就是你的垃圾解決方案？

然而事實是，簡單的思想後面，隱藏著極為深刻的數學背景。

我們搞前幾個質數出來，然後每插入一個元素，就對這些質數分別取模。

是不是要開高維數組呢？不。我們用trie的方式。（這也是「哈希樹」名字的由來）

如圖。假設我們只取前三個質數。我們拿到28，膜2為0，膜3為1，膜5為3。因此hash(28)=(0,1,3).我們把28存到上面的trie中去。

最後的效果：最底下那個「3」打上「此座已佔」標記。

假設我們用了前k個質數，那麼時間複雜度是顯然的，只需要取膜k次，每次鐵定 $O(k)$ .

空間複雜度呢？由於我們是用trie來實現的，因此對於每一個元素，最多需要開 $2+3+5+cdots p_k$ 個節點的空間，當k取8的時候，這個值為77。

甚至我們可以開更少的空間——把trie用「兄弟-兒子存法」實現。這是後話。總之空間佔用很低。

正確性呢？通過中國剩餘定理知道，我們只需要取前8個質數，就能保證約一千萬以內的數都不會出現衝突。更強的結論是，可以保證元素在連續9699690個數的值域內，不會產生碰撞。

算是令人拍案叫絕的數據結構吧。而且非常好寫。

Finger tree是個理論上好用數據結構. 我不知道看到了多少篇paper只要用finger tree的話幾句話就可以了. 我是準備哪一年有時間好好寫一個survey.

這個來自於paper.

http://www.cs.ox.ac.uk/ralf.hinze/publications/FingerTrees.pdf

(實際上有一系列更早的paper, 但是PL的人給出的抽象的描述比較好用. finger tree實際上和finger search tree/finger search有關...

可以做到以下的幾個抽象功能:

Finger tree是用來儲存一個sequence的 $S=s_1,ldots,s_n$ . 這裡每個元素來自於 $(M,cdot)$ , 一個monoid. 我們假設如果a,b in M, 則計算ab只需要O(1)時間.

1. split(S,p), $p:M o {0,1}$ is a 單調predicate, 也就是說 $p(ab)geq p(a)$ . 將sequence $s_1,ldots,s_n$ 拆成 $s_1,ldots,s_t$ 以及 $s_{t+1},ldots,s_n$ . 這裡t滿足 $p(prod_{i=1}^j s_i) = 0$ , 如果j &< t. 且 $p(prod_{i=1}^j s_i) = 1$ 如果 $jgeq t$ . 耗時 $O(log min(n,n-t))$ .

2. concat( $s_1,ldots,s_n; t_1,ldots,t_m$ ): 獲得新的sequence $s_1,ldots,s_n,t_1,ldots,t_m$ . 耗時 $O(log min(n,m))$

3. product(S), 獲得 $prod_{i=1}^n s_i$ , O(1)時間.

4. map(S,f), 獲得sequence $f(s_1),ldots,f(s_n)$ . O(1)時間. (這裡我們要求這個函數f滿足某些特殊的屬性, 比如給函數f和g, 可以O(1)時間計算函數 $h = fcirc g$ . 並且這個函數h也能在O(1)時間evaluate. 還有一個要求是f可以保證可以通過product(S)在O(1)時間獲得product( $f(s_1),ldots,f(s_n)$ ). [這個原來的paper里沒有, 可以利用lazy propagation來支持, 這裡O(1)可以變成其他的東西, 但是整個數據結構很多地方相應的要有改變...]

當然, 還需要一個O(1)時間創建一個只有一個元素的sequence的方法.

多少篇paper實際上只需要說"用finger tree,裡面的monoid是xxx"就好了. 選對了monoid. 可以保證只要幾行代碼就能實現以下的東西.

- 可以用來代替樹狀數組. 而且還能提供insert/delete呢.

- 可以做concatenatable deque, 並且還能同時計算整個deque里所有元素的sum. 就能解決這個問題

- priority queue

- rope

- 我感覺這個paper里的東西可以解決 Efficient algorithms for local ranking

- 這個arxiv文里的log-list的功能似乎就是個finger tree... http://arxiv.org/abs/1507.01512 這樣它的幾個application都可以直接拿finger tree用.

- 我還這裡寫過兩個稍微少見點的功能, 比如optimal的list merge的時間, klee measure問題.

印象最深刻的是Knuth爺爺的Dancing Links。鏈表原來可以玩得這麼溜。

理解之後會讓你興奮不已！

它的基本原理非常簡單。對於一個雙向link，一個顯然的公式是：

x.left.right ← x; x.right.left ← x;

那麼，如下操作將會把x從雙向link中刪除：

x.left.right ← x.right; x.right.left ← x.left;

它能夠高效的尋找Exact cover問題的所有解法。比如著名的Sudoku和n queens problem。

Bloom filter，拯救了多少博士生。還有靠一手Bloom filter做到大學教授了。

Cuckoo Hashing，很多系統的核心技術都有它，包括Tensorflow

另外推薦我們自己設計的Othello Hashing，查找速度快於Cuckoo Hashing數倍：

https://arxiv.org/pdf/1608.05699.pdf

並查集（Disjoint Set Union）

一行代碼，極其簡潔優美。

int find(int x) { return (x == fa[x]) ? x : (fa[x] = find(fa[x])); }

時間複雜度也很優美。路徑壓縮和按秩合併的並查集的時間複雜度是 $O(alpha(n))$ ，其中 $alpha$ 是反Ackermann函數。（謝謝評論指出筆誤。）近乎常數的時間複雜度。

我沒有學過數據結構。

但是我見過幼兒園裡，老師帶著小朋友們玩丟手絹。小朋友們圍成一大圈，而圈外拿著手絹跑動的小朋友則是這個圈的排列不斷更替的原因。

他們還玩老鷹捉小雞。每一隻小雞的手牢牢地抓住前一隻小雞的肩，第一隻小雞則抓住雞媽媽。如果不抓牢的話，馬上就會被老鷹捉去的。

小朋友們很守規矩，吃飯時排成一列，做操時排成一列，過馬路時也排成一列。

我沒有學過數據結構。

但是我去過動物園。兩隻樹袋熊掛在樹上吃樹葉：一隻比較輕，直接爬到樹梢上吃最末端的樹葉，吃完後爬回主幹，然後去往另一根枝條的末端了；另一隻比較重，不敢去樹梢，就趴在較粗的樹枝上吃，吃完了，小心翼翼地嘗試比較細的樹枝，然後，更細的。

一群錦雞雖然散亂地在籠子里分布著，但是飼養員告訴我，它們之間是有一個等級次序的。兩隻天天生活在一起的錦雞，碰巧狹路相逢的時候，是不會互不相讓地打起來的，等級低的會自動為等級高的讓路。

我沒有學過數據結構。

我去圖書館的時候，看見了兩位小姐姐坐在同一張桌子前看書。左邊的小姐姐在看《自動控制原理》，突然看不懂了，便從書架上找來《信號與系統》，放在旁邊參考。可是《信號與系統》也不太懂，於是又拿來《複變函數與拉普拉斯變換》，然後是《高等數學》。右邊的小姐姐在寫馬原論文，參考書也是一本一本地多了起來，幾乎每寫一段就要把每一本書看一看，以確認沒有寫錯。碰到這樣兩位愛學習的小姐姐，桌面顯然不夠用了，當《線性代數》被擠到桌子中間，差點把《馬克思主義簡史》碰到地上時，兩人四目相對，尷尬地笑了。

一個小夥子抱著一摞書出圖書館，結果警報響起，他便把書一本一本地拿出來，靠近檢測器，想找出是哪一本沒有借成功。圖書館的阿姨看見了，把那一摞書分成兩半，只檢測一次就找出引起警報的書再哪一半，然後是四分之一，八分之一……僅僅四次就找到那本沒有借成功的書。

圖書館的電子檢索系統，按照五層由大到小的類別給書分類，當然讀者也可以按照拼音或者筆畫來進行查找，速度都相當快。

我沒有學過數據結構。

一個醫生髮現幾個人得了一種全新的病症，便選取其中一個叫弗雷德的病人，命名這種病為弗雷德症；另一個地方的醫生也遇到同樣的情況，於是波義耳症誕生了。後來醫學界證實它們是同一種病症，於是統一稱作弗雷德症，再沒有人提及波義耳了。

我沒有學過數據結構。

但是規划出游路線的時候，我能夠在地圖上畫一條穿過所有我想去的地方的最短路線。我沒有做任何計算，也沒有任何理論能夠證明它是最短的，只是，我的直覺能夠在幾秒鐘內告訴我答案。

我也常常和別人玩這種遊戲：讓別人心裡想一個事物的名稱，然後我問他問題，他只能用「是」或「否」來回答，如果我能夠在20個問題之內猜出這個事物，就贏了。我能夠應付大多數同學，但對於腦洞大開的爸爸，我基本上沒有什麼勝算。

我沒有學過數據結構，但我體會到了她無處不在的真實的美。

=====================================================

涉及到的數據結構：

環形鏈表

鏈表/垃圾收集演算法

隊列

深度優先搜索/廣度優先搜索

有序數組

堆棧溢出

二分法

樹/哈希表

並查集

圖/旅行商問題

平衡二叉樹

作為一名退役OIer，看到這個問題實在忍不住了。

在我曾經所在的OI圈子裡，隨著近幾年黑科技的不斷誕生和引入，數據結構這塊可以說發展迅速。個人學藝不精，僅僅止步NOI Ag，那就說說僅限於OI界我所接觸到的數據結構吧。

============================================================

私以為，數據結構很大部分離不開樹的思想，容我掛一漏萬。

無論是DSU（並查集），Heap（堆），BIT（樹狀數組），SegmentTree（線段樹），四分樹，字母樹，AC自動機，後綴大家族（SA後綴數組，SAM後綴自動機，ST後綴樹），二叉搜索樹，平衡樹大家族（AVL，紅黑樹，Treap，Splay，SBT，替罪羊樹），kd-tree，PQ-tree,B樹等等都離不開樹的思想。上面提到的每個，我想每個OIer或多或少都能講出許多道道。

其他答主說到的zkw線段樹、主席樹、fhq Treap其實都是在可持久化、函數式編程的思想上衍生出來的，當然不可否認的是zkw、主席、fhq、WJMZBMR等等這些人對這方面內容在OI界的推廣和普及做出了巨大貢獻。這一塊也有很大文章可做，從可持久化棧、可持久化隊列、可持久化並查集、可持久化堆這些老牌數據結構的翻新，到可持久化線段樹（以及種種變形）、可持久化Treap這些近年來流行的數據結構思想，可持久化、函數式編程的思想可以說是近幾年OI界冉冉升起的新星。

============================================================

講了這麼多，個人覺得最優美的數據結構非Link-cut Tree莫屬。

Link-cut Tree僅在現有的Splay的基礎上加上短短几行代碼，就能完美解決動態樹的相關問題。（關於此，國家集訓隊的相關論文也有不少，我推薦大家看看fhq的總結動態樹 - fanhq666的日誌）

雖然不能說「一切皆動態樹」，但確實，有了LCT這一利器，許多樹或者環加外向樹，甚至仙人掌上的動態問題都能迎刃而解。OI界的相關題目我在這不一一贅述，僅僅選擇幾個有代表性的難題，可以說SPOJ上的QTREE系列再經典不過，而Problem 3153. -- Sone1的出現更是讓OI界掛起了一陣動態樹上子樹維護的旋風（本弱只能望而卻步），而更喪病的動態仙人掌系列Problem Set可以說將種仙人掌變成了神犇們玩轉LCT的好去處，僅僅看看VFK大爺的動態仙人掌系列題解之四――link-cut cactus的代碼就送出了我的膝蓋。

說幾個我覺得很有趣的應用，比如維護動態樹的重心、直徑、LCA（多個點）這些問題都可以用LCT解決，並且代碼量也在常人可以承受的範圍之內。

利用LCT解決動態樹優化網路流在目前OI界並不實用，但可以感覺，利用該數據結構優化後的網路流演算法在理論上邁出了很大一步。

而Self-adjusting top trees這一數據結構的出現(沒錯就是發明Splay的Tarjan)可以說又是解決動態樹問題上的里程碑，它也是LCT的繼承與發展（儘管我完全看不懂論文，也不懂這個演算法，口胡求大神輕虐）。杜教寫的TopTree僅僅用了5k+就完艹上文提到的sone1，掃一眼代碼感覺真心美如畫。

============================================================

反正我都是退役OIer了，作為嘴巴選手祝各位現役OIer好好玩有趣的數據結構噢。

Skip list.

Source: Skip list

線段樹

感覺隨著oi水平的進步

我出的數據結構題經歷了

線段樹 -&> 垃圾 -&> 線段樹

三個鮮明的階段

可持久化Treap。

它可以維護一個序列，支持單點修改，區間修改，區間信息查詢……

等等，好像太naive了？真的嗎？

在此基礎上，它還可以支持中間插入一段元素，中間刪除一段元素，翻轉一段區間，查詢特定元素的位置……

等等，好像還是太naive了？真的嗎？

在此基礎上，它還可以支持訪問之前的歷史版本，對歷史版本進行操作，還可以把若干個版本的序列拼接起來，以及把一個序列拆分成兩個序列作為兩個版本，等等……

功能相當強大！然而時間、空間複雜度只需每次操作O(logL)，其中L為序列長度。你可以把一個序列通過複製中間一段然後插在某個地方的方式使得序列長度達到10^18級別，卻只需要很少的內存來維護它。

這就是可持久化Treap的神奇之處！

dancing links...

Link-Cut Memphis!

動態樹拓展相關

Splay Tree反正是給我印象最深刻的數據結構。隨著接觸到的各種數據結構越來越多，Splay Tree的神奇之處越來越讓我讚歎。

一種不平衡的平衡搜索樹，實現了我能夠想到的所有BST所應有的操作，保證了O(logN)的單種類操作平均時間，不加入任何額外信息，十分規整而極少有「例外」的操作流程，容易理解的實現過程（雖然理解時間複雜度計算方法比較麻煩一點……）

…………為什麼說後綴自動機的這麼少…………！

……只用十幾行代碼就能擴展出無限可能………………

代碼丑還是不貼了………………

能做什麼事情…………？

由於我比較弱貼幾個簡單的好了。

以下默認字符集是常數。

最長公共子串 LCS O(N)

給出一個串S，每次詢問一個串T在S中的出現次數。

S事先給出的話構建數據結構O(|S|)，單次查詢O(|T|)。

可以在線向S的末端加入字元，單次加字元O(log|S|)，單次查詢O(T+log|S|)。

……太基礎？

我只會基礎的…………

繼續。

維護兩個字元串集合S, T，

S[0] = T[0] = ""

支持：

1. 給出i, c 令S.append (S[i] + c)

2. 給出i, c 令T.append (T[i] + c)

3. 給出i, c 令T.append (c + T[i])

4. 給出i, j 令T.append (T[i] + T[j])

5. 給出i, j詢問T[i]在S[j]中的出現次數。

離線演算法。

時間複雜度O(Nlog^2N)，其中N為操作數。

維護一個字元串集合T和字元串S，

S = T[0] = ""

支持：

1. 給出c 令S=S + c

2. 給出i, c 令T.append (T[i] + c)

3. 給出i, c 令T.append (c + T[i])

4. 給出i, j 令T.append (T[i] + T[j])

5. 給出i, l, r詢問T[i]在S[l...r]中的出現次數。

時間複雜度O(NlogN)，其中N為操作數。

去掉第一個操作而直接給出S可以在線，否則是離線演算法。

為什麼老是出現次數啊…………？

我也覺得是，換一個。

維護一個字元串序列S，支持：

1. 給出k, 串s，將s插入到S的第k個位置後

2. 給出l, r, 串T，詢問T在S[l...r]中的多少個串中出現過。

在線演算法，時間複雜度O(Nlog^2N)，其中N為操作數。

什麼…………？

你問這些東西優雅不優雅，要寫多長的代碼……？

不說這些我們還是好朋友嘛www

咦只有我一個人覺得數據結構都美嗎？

能夠想出這樣簡潔流暢地解決問題的思考方法，真是美妙呢~

分享一枚十分美麗的網址

http://visualgo.net/

從問題抽象的意義和問題的普遍性來說，當然是有向無環圖DAG - Directed Acyclic Graph，因為它是一種最通用的數據結構，適用於表達太多的問題，最切合用計算機解決問題的思維方式。

常見的樹結構也算是DAG的一種特殊情形。樹結構體現的是單純的分支，而DAG體現的是分支和匯合併存。

我印象最深刻的有幾個實例：

1. 搜索類問題和動態規劃：搜索類問題通常會藉助樹結構來描述問題結構。當存在最優子結構時，問題結構就變成了DAG；

2. 拓撲排序：對順序約束進行建模的理念；

3. 代碼類型推導中的共同子表達式；

4. 函數式編程中的Persistent Data Structure；

5. 基因演算法中的Repair Loop；

太多了，不一一列舉。

哈希表，不解釋

2-3 tree. 老師在上課的時候把它叫做data structure from the book...仿照Erd?s的proof from the book…大概是因為解決binary search tree balance問題的一個簡易優雅並且自然的方法，比AVL和red black tree都方便多了

操作數組

專門用來處理沒有詢問的題

例題：

區間平方，區間加一個數

沒有詢問操作，但是要誠實

只需要十分誠實地把所有操作存下來，詢問的時候處理對答案的貢獻即可。

———————————————

抖機靈完畢，以下為正經回答

並查集。

並查集可以離線解決許多區間信息和詢問——Claris

舉兩個例子

第一個來自算導

用並查集離線處理一個優先隊列的插入和刪除最大值操作，並回答

第二個來自經典問題

區間染色（修改為同一個值），所有修改完後求整個序列每個點顏色（權值）

第一題思路大概是把刪除操作看作將插入分成若干部分，然後將插入的數從小往大排序，用並查集從小往大維護每個數是在哪次刪除操作中刪掉的

第二題思路大概是記錄每個位置右邊第一個沒有被染過顏色的點，用並查集壓縮路徑

不想具體講細節了...就這樣吧

————————————

以下可能比較難懂，無視就好

一個聽說叫做compact SAM的東西也能用類似的思想壓縮路徑來減少在SAM上DFS的時間...反正非常妙就對了...詳情http://oscar.blog.uoj.ac/blog/2935

我就是從評論區的zqc霸霸那裡了解到這個東西的名字的QWQ