本文共 1053 字，大约阅读时间需要 3 分钟。

RMQ（Range Minimum/Maximum Query）

目的：针对多次询问区间的最值问题。

解释

二维数组 dp[i][j] 表示从第 i 位开始连续 2^j 个数中的最小值。

模板代码

void rmq_init() {
       for (int i = 1; i <= N; i++)        //初始化，arr为初始输入数组        dp[i][0] = arr[i];    for (int j = 1; (1 << j) <= N; j++)        for (int i = 1; i + (1 << j) - 1 <= N; i++)            dp[i][j] = min(dp[i][j - 1], dp[i + (1 << j - 1)][j - 1]);}int rmq_query(int l, int r) {
       int k = log2(r - l + 1);    return min(dp[l][k], dp[r - (1 << k) + 1][k]);}

转载地址：https://blog.csdn.net/weixin_43820352/article/details/108564042 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！