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

范式化的区间最值查询（RMQ）问题

一、RMQ问题概述

RMQ（Range Minimum/Maximum Query）问题是指在给定的数列中，回答多个关于特定区间内最小值或最大值的查询请求。每个查询的形式为 RMQ(A, i, j)，要求找出数列A中从索引i到j（包括i和j）区间内的最小值或最大值。

1.1 时间复杂度目标

• 预处理时间：O(n log n)
• 每次查询时间：O(1)

二、ST表预处理技术

ST表（Segment Tree Table）是一种高效的数据结构，用于解决区间最值查询问题。ST表通过预处理，将区间最值查询转化为对预处理后的表的简单数组查询。

2.1 ST表的构建步骤

2.2 预处理的关键点

• 块大小：通常设为2的幂次方，例如m = floor(log2(n))。
• 分块处理：对于每个块，预处理其内部的最值信息，并将块作为基本单位进行ST表构建。

2.3 ST表的查询方法

通过查询预处理好的ST表，可以快速找到任意区间的最小值或最大值。

三、约束RMQ问题

约束RMQ问题是指数列满足特定约束条件下的RMQ问题。常见的约束条件包括相邻元素的差值固定（如±1），这使得数列具有某种规律性。

3.1 分块处理方法

对于约束RMQ问题，通常采用分块的方法：

3.2 处理边角料

边角料是指区间的开头和结尾部分，通常需要单独处理。通过预处理这些小块的信息，可以快速得到最值。

3.3 时间复杂度分析

• 预处理：O(n log n)
• 查询：O(log n)

四、笛卡尔树的应用

笛卡尔树是一种特殊的二叉搜索树，具有以下特性：

4.1 笛卡尔树的构建

• 初始化：将数列中的元素按顺序插入到笛卡尔树中。
• 插入规则：每次插入元素时，将其插入到合适的位置，使得中序遍历结果保持递增。

4.2 RMQ与LCA的转化

笛卡尔树可以用来解决RMQ问题，通过将其转化为LCA（最低公共祖先）问题。具体步骤如下：

4.3 LCA的应用

通过访问序列，可以快速找到两个节点的LCA，从而确定区间的最值。

五、具体实现示例

5.1 ST表实现

namespace STtable {    const int MaxN = 363640, LogN = 19;    int st[MaxN][LogN], duishu[MaxN], item[MaxN];        void init(const int[] shuzu, int n) {        for (int i = 0; i <= n; ++i)            st[i][0] = i, item[i] = shuzu[i];        for (int j = 1; (1 << j) - 1 <= n; ++j)            for (int i = 0; i + ((1 << j) - 1) <= n; ++i) {                int x = st[i][j-1];                int y = st[i + (1 << (j-1))][j-1];                if (item[y] < item[x])                    st[i][j] = y;            }        for (int i = 2; i <= n+1; ++i)            duishu[i] = duishu[i > 1] + 1;    }        int query(int l, int r) {        if (l > r) swap(l, r);        int k = duishu[r - l + 1];        int x = st[l][k], y = st[r - (1 << k) + 1][k];        return item[x] < item[y] ? x : y;    }}

5.2 约束RMQ实现

namespace narrowRMQ {    const int MaxN = 4000000, Block = 11;    int benzhi[1 << Block][Block][Block];    int inside[(MaxN * Block) + 1], item[MaxN];        void init(const int[] shuzu, int n) {        for (int i = 1; i <= n; ++i)            item[i] = shuzu[i];        for (int s = 0; s < (1 << Block); ++s)            for (int l = 1; l < Block; ++l) {                int now = 0, all = 0, id = l - 1, r = l;                for (int i = 0; (1 << j) - 1 <= n; ++j) {                    if (s > r) ++now;                    else if ((--now) < all)                        id = r, all = now;                    benzhi[s][l][r] = id;                }            }        for (int i = 0; i <= n / Block; ++i)            data[i] = infinity;        for (int i = 1; i <= n; ++i) {            int k = i / Block;            if (item[i] < data[k])                data[k] = item[i];                best[k] = i;        }        STtable::init(data, n / Block);    }        int query(int a, int b) {        if (a > b) swap(a, b);        if (a == b) return a;        int l = a / Block, r = b / Block;        int L = inside[l], R = inside[r];        if (l == r)            return benzhi[L][a + 1][b] + l * Block;        int res = 0, x = 0;        if (l + 1 <= r - 1)            x = STtable::query(l + 1, r - 1);            if (data[x] < item[res])                res = best[x];        x = a + l * Block;        if (a != Block - 1)            x = benzhi[L][a + 1][Block - 1] + l * Block;        if (item[x] < item[res])            res = x;        x = b + r * Block;        if (b != 0)            x = benzhi[R][1][b] + r * Block;        if (item[x] < item[res])            res = x;        return res;    }}

5.3 笛卡尔树实现

namespace Descartes {    const int MaxN = 2000000;    int son[MaxN | 1][2], meet[MaxN < 1], depth[MaxN < 1], dfn;    int first[MaxN | 1];        void dfs(int o, int deep) {        meet[++ dfn] = o, depth[dfn] = deep;        first[o] = dfn;        for (int i = 0; i < 2; ++i)            if (son[o][i])                dfs(son[o][i], deep + 1);        meet[++ dfn] = o, depth[dfn] = deep;    }        void init(int[] shuzu, int n) {        static vector
   
     v;        v.clear();        v.push_back(0);        shuzu[0] = -infinity;        for (int i = 1; i <= n; ++i) {            while (v.back() != i && shuzu[v.back()] > shuzu[i])                v.pop_back();            son[i][0] = v.back(), son[v.back()][1] = i;        }        dfn = 0;        dfs(son[0][1]);    }}
   

六、代码示例

namespace normalRMQ {    void init(int[] shuzu, int n) {        Descartes::init(shuzu, n);        narrowRMQ::init(Descartes::depth, Descartes::dfn);    }        int query(int l, int r) {        l = Descartes::first[l], r = Descartes::first[r];        return Descartes::meet[narrowRMQ::query(l, r)];    }}

七、总结

RMQ问题是计算机科学中的经典问题，通过预处理和高效的数据结构，可以在O(n log n)的时间预处理后，实现O(1)的查询时间。ST表和笛卡尔树都是解决RMQ问题的经典方法，各有其适用场景。理解这些技术，对于解决实际问题具有重要意义。

转载地址：http://xgvq.baihongyu.com/