倍增-总结
序列
前2题题意：https://blog.csdn.net/weixin_52536621/article/details/127104830
区间分段
考虑进行预处理每个数如果只能有一段到达的位置，再进行倍增，最后倍增跳跃即可。
最优贸易简化版
预处理每个点向后走 \(2^j\) 不的最小买入价格、最大卖出价格、最大收益。
天才ACM
这题真正把二分和倍增拉开差距了。如果用二分，每次需要 \(O(n\log n)\) 的时间，那么如果段很小，那么需要 \(O(n^2 \log n)\)，如果用倍增，只需要将其拆解成 \(\log\) 段，每段是 \(O(n\log n)\)，那么则只需 \(O(n\log^2 n)\)，效率远超二分。如果再用二路归并优化，只对新增部分排序，那么可以进一步优化成 \(O(n\log n)\)。
https://www.acwing.com/activity/content/code/content/5464657/
树上
LCA+习题
母题-P3379 【模板】最近公共祖先（LCA）
https://www.luogu.com.cn/article/oatnrw81
P1084 [NOIP2012 提高组] 疫情控制
最小值问题，考虑二分，然后贪心地让每个军队尽可能往上（使用倍增）。
运输计划
最小值问题，考虑二分，然后根据 \(mid\) 删边，运用树上差分求满足公共要求的路径，对于每个点求子树和，注意求子树和可以利用 dfs 序的逆序。
天天爱跑步
由于每个玩家是一条路径，运用树上差分标记玩家，注意记录的值可以没有意义。
其他技巧
若干点 \(\text{LCA}=\text{LCA}(\text{dfs序}\min, \text{dfs序}\max)\)
总结
线性的倍增
一般记录从位置 \(i\) 往后跳 \(2^j\) 步的信息；
树上的倍增
一般记录从点 \(i\) 往父节点方向跳 \(2^j\) 步的信息；
可以与二分结合，也可能在某些问题的处理上优于二分。
可以与树上的其他知识点，如 dfs 序、差分。