第2章　區(qū)間信息維護與查詢

2.1　倍增、ST、RMQ

原理1　倍增

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

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

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