無旋Treap，又稱fhq_treap，是由范浩強大佬發明的一種高效數據結構。它在性能上兼具了Treap和Splay的特性，既比Treap易于學習，又比Splay在實際應用中表現出更高的效率。適合處理各種平衡樹操作，包括插入、刪除、搜索等，同時支持持久化操作（雖然本篇博客不涉及這部分內容）。它的樹高期望大小為log級別，因此常數遠小于Splay，適用于復雜數據結構和算法的優化。無旋Treap的核心思想是結合了樹的二叉搜索樹性質和堆的性質。在二叉搜索樹的基礎上，每個節點都被賦予了一個隨機的優先級（權值）。這種隨機性確保了樹的結構在多次操作后能夠保持平衡，從而使得操作復雜度的期望值為log級別。無旋Treap的兩種基本操作是分裂(Split)和合并(Merge)。分裂操作將樹分為兩個子樹，其中左子樹的最大點權小于等于右子樹的最小點權，操作的復雜度期望為log級別。合并操作則將兩個子樹合并成一棵，同樣保證左子樹的最大點權小于等于右子樹的最小點權，通過隨機選擇節點作為根節點，可以確保樹的平衡性。以下是基于無旋Treap的幾種常見操作實現的示例代碼。例如，插入節點時，首先創建新節點，然后根據權值將節點拆分成左右子樹，之后使用Merge操作將左右子樹與新節點合并。同樣，刪除節點的操作也是通過分裂操作來實現的。對于區間操作，可以通過分裂操作將目標區間表示的子樹拆分出來，然后在根節點上進行標記，最后通過合并操作來完成操作。本文中還提供了幾個實例問題的解決方案，如洛谷3369普通平衡樹、洛谷3391文藝平衡樹和洛谷3372線段樹等問題，這些示例代碼展示了如何利用無旋Treap進行插入、刪除和區間操作，從而高效解決問題。對于學習和使用無旋Treap有興趣的讀者，推薦閱讀相關資料，了解更深入的實現細節和優化技巧。同時，也可以在交流平臺與作者互動，獲取更多關于算法和數據結構的信息。為了便于學習，提供了一個PDF文件鏈接，以及作者的交流渠道和更多算法題解資源鏈接。