第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仍不相等，返回查找失败。