稀疏表常用于解决RMQ问题（区间最大/小值查询问题），稀疏表仅支持高效的查询操作，并不支持动态修改操作。其实现主要基于倍增思想和动态规划。
稀疏表最主要的思想就是将区间分为两个子区间，例如[l,r]分成[l,l+2^k-1]和[r-2^k+1,r]，其中k=log2(r-l+1)向下取整。
其本质上就是用两个长度为 2^k 的重叠区间覆盖 [l,r]，那我们查询区间最值就可以分解为两个子区间最值中的较大/小值，即max[l,r]=max(max[l,l+2^k-1],max[r-2^k+1,r])。
我们用二维数组构造稀疏表，大小为f[N][log2(N)+1]，其中f[i][j]=max[i,i+2^j-1]，状态转移方程为f[i][j]=max(f[i][j-1],f[i+2^(j-1)][j-1]);
vector<int> dt(N);
vector<vector<int>> f(N,vector<int>(log2(N)+1));
void init(int n){
for(int i=0;i<n;i++) f[i][0]=dt[i];
for(int j=1;(1<<j)<=n;j++){
for(int i=0;i+(1<<j)-1<n;i++){
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
}
int query(int l,int r){
int k=log2(r-l+1);
return max(f[l][k],f[r-(1<<k)+1][k]);
}
