rmq
rmq是求区间的最大或者最小值的，但不可以修改值，时间复杂度nlgn,空间复杂度nlgn
开辟了n*lgn的二维数组，也就是ma[n][lgn],mi[n][lgn]分别代表最大和最小
对于ma[i][j]代表，a[i]~a[i+(1<<j)-1]中最大的值 1<<j其实就是2的j次幂
所以初始化数组，ma[i][j]=max(ma[i][j-1],ma[i+(1<<(j-1))][j-1])，其实就是把2^j的区间分成两半，这两块最大值中较大的就是整个区间最大值，mi数组同理
void init()
{
for(int i=1;i<=n;i++)
ma[i][0]=a[i];
for(int j=1;(1<<j)<=n;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
{
ma[i][j]=max(ma[i][j-1],ma[i+(1<<(j-1))][j-1]);
}
}
}
对于查询一个区间l~r的最大值，因为任何一个区间长度len一定是存在 2^k<=len<2*2^k,那么我们如果找到k, ma[l][k]和ma[r-(1<<k)+1][k]一定覆盖整个区间
int rmqma(int l,int r)
{
int k=log2(r-l+1);
return max(ma[l][k],ma[r-(1<<k)+1][k]);
}
优质内容筛选与推荐>>1、操作系统学习笔记 进程
2、url获取参数
3、mysql 数据类型
4、【儿童成长心理学】第一章 引言
5、一个文字在一个图片上水平居中，并且悬浮变大特效