在我們學習認識后綴平衡樹之前，一定要先了解什么是重量平衡樹？所謂的重量平衡樹是保證操作影響的最大子樹大小是最壞的或均攤的或期望的O(logn)。
那什么是后綴平衡樹？后綴平衡樹是一種動態(tài)維護后綴排序的數(shù)據(jù)結構。具體而言,它支持在串S的開頭添加/刪除一個字符。
后綴之間的大小由字典序定義，后綴平衡樹就是一個維護這些后綴順序的平衡樹，即字符串T的后綴平衡樹是T所有后綴的有序集合。后綴平衡樹上的一個節(jié)點相當于原字符串的一個后綴。特別地，后綴平衡樹的中序遍歷即為后綴數(shù)組。
后綴平衡樹的優(yōu)點：
（1）后綴平衡樹的思路比較清晰，相比后綴自動機等后綴結構更好理解，會寫平衡樹就能寫。
（2）后綴平衡樹的復雜度不依賴于字符集的大小
（3）后綴平衡樹支持在字符串開頭刪除一個字符
（4）如果使用支持可持久化的平衡樹，那么后綴平衡樹也能可持久化
后綴平衡樹的應用：
（1）字符串匹配
（2）給定S和數(shù)個T,每次詢問T在S中出現(xiàn)了幾次。
（3）因為已經(jīng)后綴排序,只要找到第一個嚴格小于T的最后一個后綴和嚴格大于T的第一個后綴即可。
（4）匹配時直接暴力。總復雜度為O((|S|+∑|T|)log|S|)。
關于后綴平衡樹的一些知識點都已經(jīng)羅列出來了，這些都是最需要掌握的基礎知識，便于大家在做題中，及時作出正確的判斷。
C語言網(wǎng)提供由在職研發(fā)工程師或ACM藍橋杯競賽優(yōu)秀選手錄制的視頻教程，并配有習題和答疑，點擊了解：
一點編程也不會寫的：零基礎C語言學練課程
解決困擾你多年的C語言疑難雜癥特性的C語言進階課程
從零到寫出一個爬蟲的Python編程課程
只會語法寫不出代碼？手把手帶你寫100個編程真題的編程百練課程
信息學奧賽或C++選手的 必學C++課程
藍橋杯ACM、信息學奧賽的必學課程：算法競賽課入門課程
手把手講解近五年真題的藍橋杯輔導課程