倍增法
通常计算\([i,n]\)区间的所有情况的时间复杂度为\(O(n^2)\)，而用倍增法只需\(O(nlogn)\)的复杂度就能表示出\([i,n]\)区间的所有情况。
求第i的下2^j个节点
当给出的数据中任意元素只能单向通向令一个唯一元素时，设\(fa[i][j]\)为第\(i\)个元素的下\(2^j\)个节点，可以得到以下递推公式。
for(int j = 1; j < 31; j++) {//j的大小根据数据范围确定
for(int i = 1; i <= n; i++) {
fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
}
维护区间值
设\(mul[i][j]\)为区间\(i\)到\(i+2^j\)所有元素的乘积，可以得到以下递推公式。
for(int j = 1; j < 31; j++) {
for(int i = 1; i <= n; i++) {
mul[i][j] = mul[i][j - 1] * mul[fa[i][j - 1]][j - 1];
}
}
设\(add[i][j]\)为区间\(i\)到\(i+2^j\)所有元素之和，可以得到以下递推公式。
for(int j = 1; j < 31; j++) {
for(int i = 1; i <= n; i++) {
add[i][j] = add[i][j - 1] + add[fa[i][j - 1]][j - 1];
}
}
从上面两个例子可以看出，区间\([i,i+2^j]\)的维护值是从\([i,i+2^{j-1}]\)和\([i+2^{j-1},i+2^j]\)推出来的。
查询区间值
以上面两个例子为例
查询区间\([l,r]\)乘积
for(int j = 30; j >= 0; j--) {
if(r >= (1 << j)) {
r -= (1 << j);
ans *= mul[l][j];
l = fa[l][j];
}
}
查询区间\([l,r]\)之和
for(int j = 31; j >= 0; j--) {
if(r >= (1 << j)) {
r -= (1 << j);
ans += add[l][j];
l = fa[l][j]
}
}
可以看出，每次查完区间\([l,l+2^j]\)，把\(l\)移到\(l+2^j\)处，再进行下一次查询。