Sprooc

所谓“倍增”，就是成倍增长。在一些求解空间较大的问题中，如果使用通常的线性递推，需要线性的时间复杂度。而如果采用倍增的方式，通常能优化为对数时间复杂度。简单地解释倍增思想，就是每次都试图使结果范围扩大一定长度，如果扩大后仍满足要求，则扩大，并将下一次试图扩大的长度变为原来的两倍；若不满足，则将扩大长度减半，再次尝试，若仍不满足，则继续减半。最终，扩大长度减为0，就得到了所需的结果。下面是两个使用倍增算法的例子。 求小于T的最大数组前缀和 给定一个长度为N的数列 A，然后进行若干次询问，每次给定一个整数T,求大的 k，满足 $\sum_{i=1}^{N}{A[i]}\le T$。你的算法必须是在线的（必须即时回答每一个询问能等待收到所有询问后再统一处理），假设$0\le T\le\sum_{i=1}^{N}{A[i]}$。 最朴素的做法当然是从前往后累加数组，直到累加和大于T，时间复杂度是O(N)。 首先用O(N)的时间预处理，求出前缀和数组，再用二分查找确定小于等于T的上界。每次查找O(logN)。 如果每次查找的T都很小，使用二分查找可能还不如直接从头遍历数组，那么可以使用倍增算 ...