第2章　區間信息維護與查詢

2.1　倍增、ST、RMQ

原理1　倍增

任意整數均可被表示成若干個2的次冪項之和。例如整數5，其二進制表示為101，該二進制數從右向左第0、2位均為1，則5=22+20；整數26，其二進制表示為11010，該二進制數從右向左第1、3、4位均為1，則26=24+23+21。也就是說，2的次冪項可被拼成任一需要的值。

倍增，顧名思義就是成倍增加。若問題的狀態空間特別大，則一步步遞推的算法復雜度太高，可以通過倍增思想，只考察2的整數次冪位置，快速縮小求解范圍，直到找到解。

例如在一棵樹中，每一個節點的祖先都比該節點大，要查找4的祖先中等于x的祖先節點。最笨的辦法就是一個一個地向上比較祖先節點，判斷哪一個等于x。若樹特別大，則搜索效率很低。雖然祖先是有序的，但不是按順序存儲的，無法得到中間節點的下標，因此不可以采用普通的二分搜索，這時怎么辦呢？答案是采用倍增思想：將x和當前節點向上2i個節點進行比較，若x大于該節點，則向上跳2i個節點，加大增量2i+1，繼續比較；若x小于該節點，則減少增量2i-1，繼續比較，直到相等，返回查找成功；或者增量減為20仍不相等，返回查找失敗。