二进制的启示

在学习数论时我们都知道：只用 2 的幂次可以组合出所有的正整数。这便是二进制的魅力——状态简单而又变化万千。

引子

实际算法中，常常有一些线性的但数据量特别大的问题，如区间求和、求最小值等。很多时候，为了把时间复杂度从 $O(n^2)$ 甚至更高的地方降下来，我们需要对数据进行一些预处理，以提高计算的速度。在这其中，有很大一部分是来自二进制运算特点的启发。

目录

1. 树状数组
2. RMQ
3. LCA&树上倍增

作者：hsfzxjy
链接：
许可：CC BY-NC-ND 4.0.
著作权归作者所有。本文不允许被用作商业用途，非商业转载请注明出处。