求高效RMQ算法：查询区间内大于定值的最小元素

问题回顾 #

给定正整数序列$a_1,…,a_N$，对每个查询$(l, r, d)$，找出区间$[l, r]$内大于$d$的最小元素，即求$\min{a_i \mid l ≤ i ≤ r, a_i > d}$。

你尝试了线段树+稀疏表的组合算法，理论复杂度$O(N \log N + Q \log N)$但实际运行过慢，结合你提供的代码，先分析实现中的关键错误：

代码中的致命实现问题 #

1. 稀疏表的LOG_N设置过小 #

MAX_N = 100005，而$\log_2(100005) ≈ 17$，但你设置LOG_N = 10，这意味着稀疏表只能处理长度≤$2^{10}=1024$的区间。当查询区间长度超过1024时，k = 31 - __builtin_clz(length)会得到大于等于10的值，触发k >= LOG_N的判断返回-1，导致本该用稀疏表直接返回的场景错误进入线段树递归，大幅增加查询开销。

2. 线段树未初始化容量 #

你使用std::vector<int32_t> segment_tree但未提前分配足够空间。递归构建时直接赋值segment_tree[p]会导致vector频繁扩容，甚至访问非法内存，这不仅慢，还可能引发未定义行为。正确的做法是提前将segment_tree的大小设为$4*MAX_N$（线段树的标准空间需求）。

3. 递归查询中冗余的稀疏表调用 #

在query_segment_tree的递归函数开头，每次都调用query_sparse_table(i,j)，这会在每一层递归都额外执行一次稀疏表查询，带来不必要的常数开销。而且因为LOG_N的问题，这个判断大部分时候失效，完全起不到加速作用。

4. 线段树查询逻辑冗余 #

当当前节点区间完全匹配查询区间时，判断segment_tree[p] > d后直接返回，但这个判断和稀疏表的判断重复，且因为稀疏表的错误设置，很多时候会无效进入递归分支。

修复后的核心代码调整 #

修正LOG_N与稀疏表 #

const int32_t MAX_N = 100005;
const int32_t LOG_N = 17; // 适配1e5的长度
int32_t sparse_table[MAX_N][LOG_N];

提前初始化线段树空间 #

在构建线段树前添加：

segment_tree.resize(4 * MAX_N);

简化线段树查询逻辑（移除冗余的稀疏表调用） #

修改后的查询函数：

int32_t query_segment_tree(int32_t p, int32_t l, int32_t r, int32_t i, int32_t j, int32_t d)
{
    if (i > j) {
        return -1;
    }
    // 当前区间所有元素都<=d，直接返回-1
    if (segment_tree[p] <= d) {
        return -1;
    }
    // 叶子节点，且元素>d，返回该值
    if (l == r) {
        return segment_tree[p];
    }
    int32_t m = (l + r) / 2;
    int32_t ql = query_segment_tree(2 * p, l, m, i, std::min(j, m), d);
    int32_t qr = query_segment_tree(2 * p + 1, m + 1, r, std::max(i, m + 1), j, d);
    // 合并左右结果：取存在的最小值，都不存在返回-1
    std::vector<int32_t> valid;
    if (ql != -1) valid.push_back(ql);
    if (qr != -1) valid.push_back(qr);
    return valid.empty() ? -1 : *min_element(valid.begin(), valid.end());
}

如果想保留稀疏表加速全区间>d的情况，应该只在最外层查询时调用一次稀疏表，而不是递归每层都调用：

int32_t query(int32_t l, int32_t r, int32_t d)
{
    int32_t st_min = query_sparse_table(l, r);
    if (st_min > d) {
        return st_min;
    }
    return query_segment_tree(1, 0, deviations.size() - 1, l, r, d);
}

更高效的算法选项 #

如果修复后还是不够快，可以尝试以下更优的在线/离线方案：

1. 小波树（Wavelet Tree） #

• 预处理复杂度：$O(N \log M)$，$M$是序列的最大值。
• 查询复杂度：$O(\log M)$，常数极小，适合大数据量的查询场景。
• 核心思想：将值域分层，每层维护元素的位置信息，查询时通过二分值域快速定位大于d的最小元素。

2. 笛卡尔树+倍增 #

• 预处理复杂度：$O(N \log N)$。
• 查询复杂度：$O(\log N)$，常数比线段树小。
• 核心思想：构建序列的笛卡尔树（父节点是区间最小值的二叉树），然后对每个节点倍增预处理祖先信息，查询时通过笛卡尔树快速定位区间内的候选元素。

3. 离线处理+单调栈 #

如果所有查询可以提前获取：

• 将序列元素和查询按d排序，用单调栈维护当前大于d的元素集合，再结合前缀最小值数组处理区间查询，整体复杂度$O(N \log N + Q \log Q)$，适合离线场景。

内容的提问来源于stack exchange，提问作者Yeladia