倍增

[最近公共祖先（LCA）](https://www.luogu.com.cn/blog/TheDawn/qian-xi-lca) [LCA代码](https://www.luogu.com.cn/paste/zun6v1td) 倍增经常被用于求区间的最值。 求一段区间的和可以预处理出前缀和然后相减，但是求一段区间的最大值就不可以了。 求一段区间的最值时，我们可以把这段区间分成若干段，对于每一段求一个最值，最后合并起来。却不能将区间分成一个区间减去另一个区间。 如果每次询问区间最值时再去算，则会太慢。如果先预处理出所有区间的最值，又存不下。所以只好折中一下，只算出一部分的区间的最值，询问的时候再合并。 所以我们找到其中的平衡点，即预处理用O(nlogn)的时间，每次查询用O(logn)的时间。 记录以每个点开始，长度为1、2、4、8……的区间的最值，那么查询的时候只需要合并logn个区间即可（甚至可以合并两个部分重合的区间也可以）。 这种方法可以算出区间的各种值，比如gcd、lcm，第k大值等。