稀疏表构建：内层循环条件为何用j + (1 << i) <= N而非j + (1 << (i-1)) <= N？

开发者阿泽

2026-7-17

稀疏表实现中内层循环终止条件的疑问

在稀疏表的实现里，有些代码的循环终止条件和循环内的访问操作看起来不匹配，比如CP Algorithms里的这段实现：

for (int i = 1; i <= K; i++)
    for (int j = 0; j + (1 << i) <= N; j++)
        st[i][j] = f(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);

为什么内层循环用j + (1 << i) <= N，而不是j + (1 << (i-1)) <= N？

要搞懂这个问题，得先明确稀疏表st[i][j]的含义：它代表从下标j开始，长度为2^i的区间的查询结果（比如区间最大值、最小值这类可重复贡献的操作）。

那内层循环的终止条件j + (1 << i) <= N，本质是保证整个长度为2^i的区间都落在数组的有效范围内——从j到j + 2^i - 1的所有下标都不超过N-1（假设数组下标从0开始）。

如果换成j + (1 << (i-1)) <= N，那只能保证j + 2^(i-1) -1不越界，但循环里我们要访问的是st[i-1][j + (1 << (i-1))]，这个位置对应的区间是从j + 2^(i-1)开始，长度为2^(i-1)的区间，它的结束下标是j + 2^(i-1) + 2^(i-1) -1 = j + 2^i -1，这时候如果j + 2^(i-1) <= N，但j + 2^i > N的话，这个结束下标就会越界，导致访问非法内存。

举个具体例子：假设N=5，i=2（也就是2^i=4），如果用j + 2^(i-1) <= N（也就是j+2<=5），那j可以取到3，这时候j + 2^(i-1)=3+2=5，而数组下标最大是4，访问st[1][5]就越界了。但用j + 4 <=5的话，j最多取1，j+4=5<=5，对应的结束下标是1+4-1=4，刚好在范围内，同时j+2^(i-1)=1+2=3，st[1][3]对应的区间是3到4，也完全合法。