RMQ区间求最值 后缀数组height预处理(区间求最小值)

本文主要是介绍RMQ区间求最值 后缀数组height预处理(区间求最小值)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

首先是一般的RMQ区间求最值问题

minsum[i][j]表示起始位置为i长度为j的区间内的最小值。RMQ利用二进制优化处理。

所以，他的状态转移方程就是  F[i, j]=max（F[i，j-1], F[i + 2^(j-1)，j-1]）

查询区间[i][j]的最小值相当于区间[i][k]和区间[t][j]的最小值，其中k>=t

void RMQ(int num)
{for(int j = 0; j < 19; ++j)for(int i = 1; i <= num; ++i){if(j==0)minsum[i][j]=arr[i];//初始化else if(i + (1 << j) - 1 <= num){minsum[i][j] = min(minsum[i][j - 1], minsum[i + (1 << (j - 1))][j - 1]);//此处为区间求最小值  如果要求最小值，把min相应的改为max就好}}
}

我是在学习后缀数组的时候接触到RMQ算法的，下面的代码是求suffix（i）跟suffix（j）的最大公共前缀的RMQ预处理

对于RMQ部分基本没有变化，只是初始化的时候arr改称了height数组

void init()//获取相对应的最长长度Log[i]=j表示2^j<=i并且j是满足条件的最大值
{Log[0] = -1;for(int i=1; i<=maxn; i++){Log[i]=(i&(i-1))?Log[i-1]:Log[i-1] + 1 ;}
}
int val(int x,int y)//x，y表示要比较的以x位置开头的后缀与以y开头的后缀
{if(x==y)return 1111111;x=rank[x];y=rank[y];int i=min(x,y);int j=max(x,y);i++;int tem=Log[j-i+1];return min(minsum[i][tem],minsum[j-(1<<tem)+1][tem]);
}

刚刚学习后缀数组，有写的不妥的地方还望指正。

这篇关于RMQ区间求最值 后缀数组height预处理(区间求最小值)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---