【算法2-3】分治与倍增

如果想知道我国的人口数量，就需要进行人口普查。让每一个省份都去统计本省有多少人， 然后将各省人口累加起来，就可以获得全国的人口数量。而要想知道某一个省的人口数量，可以 让省里的每一个城市统计本市有多少人，然后将各市人口累加起来，就可以获得这个省的人口数 量……以此类推，层层细分，最后统计一个村子或者一个小区有多少人，这个任务就很简单了。 把一个复杂的问题细分成若干结构相同但规模更小的子问题，然后将每个子问题的解合并起来， 就得到了复杂问题的解，就是本章将会介绍的分治策略。 本章的最后还介绍了倍增算法。将一个较大的数字分为若干个 $2^i$ 的和，同时维护所有长度为 $2^i$ 的区间，可以解决一些特定的问题，例如区间求最值的问题。 对应进阶篇第 3 章。