定义法 $O(n)$

记

$$
k = \lfloor log_2n \rfloor
$$

则

$$
\begin{aligned}
log_2n - 1 < k \le log_2n
\end{aligned}
$$

则

$$
\begin{aligned}
2^k \le n < 2^{k + 1}\\
\end{aligned}
$$

由于 $log_2n$ 和 $\lfloor x \rfloor$ 都是单调增函数，则 $\lfloor log_2n \rfloor$ 也是，可用双指针优化。

for (int i = 2, j = 1; i <= n; i++) {
  while (1 << j + 1 <= i) j++;
  lg2[i] = j;
}

上述代码中，内层 while 总共执行 $log_2n$ 次，可忽略不计。

递推法 $O(n)$

由

$$
\begin{aligned}
log_2n &= log_2(\frac{n}{2} \times 2) \\
&= log_2 \frac{n}{2} + log_22 \\
&= log_2 \frac{n}{2} + 1
\end{aligned}
$$

得

$$
\begin{eqnarray}
\lfloor log_2n \rfloor &= \lfloor log_2 \frac{n}{2} + 1 \rfloor \\
&= \lfloor log_2 \frac{n}{2} \rfloor + 1 \\
&= \lfloor log_2 \lfloor \frac{n}{2} \rfloor \rfloor + 1 \tag{1}
\end{eqnarray}
$$

关于式 $(1)$，若 $n$ 为偶数显然成立。若 $n$ 为奇数

设

$$
n = 2k + 1, k \in \mathbb{N^{+}}
$$

则

$$
\begin{aligned}
& \frac{n}{2} = k + \frac{1}{2} \\
& \lfloor \frac{n}{2} \rfloor = k
\end{aligned}
$$

设

$$
2^m \le k < 2^{m + 1}, m \in \mathbb{N}
$$

则

$$
2^m \le k + \frac{1}{2} < 2^{m + 1}
$$

则

$$
\lfloor log_2k \rfloor = \lfloor log_2(k + \frac{1}{2}) \rfloor = m
$$

则

$$
\lfloor log_2\lfloor \frac{n}{2} \rfloor \rfloor = \lfloor log_2\frac{n}{2} \rfloor
$$

for (int i = 2; i <= n; i++) lg2[i] = lg2[i >> 1] + 1;