我试图解决一些范围最小值查询，其中最小值必须高于某个常数。
问题：
给定一些正整数a1，... aN，对于整数l，r，d的每个查询，找到仍然大于d的最小元素，即findmin {a_i|l〈= i〈= r，a_i〉d}。
我已经尝试了segment tree算法，当所有元素都大于d时，使用额外的sparse table来加快查询速度。这给我带来了O（N * log（N）+Q * log（N））的复杂度。使用稀疏表并没有改善复杂度，但它削减了很多对段树查询的调用。
不过，这个算法还是太慢了，有没有人有更快的算法让我试试？
编辑：
人们指出这与我的实现有关，我使用了正确的数据结构，所以这是我的代码，也许我做错了什么，增加了复杂性：

#include <bits/stdc++.h>

const int32_t MAX_N = 100005;
const int32_t LOG_N = 10;
int32_t sparse_table[MAX_N][LOG_N];

std::vector<int32_t> deviations;
std::vector<int32_t> segment_tree;

void build_sparse_table(int32_t N)
{
    for (int32_t i = 0; i < N; i++) {
        sparse_table[i][0] = deviations[i];
    }
    for (int32_t k = 1; k < LOG_N; k++) {
        for (int32_t i = 0; i + (1 << k) - 1 < N; i++) {
            sparse_table[i][k] = std::min(sparse_table[i][k - 1], sparse_table[i + (1 << (k - 1))][k - 1]);
        }
    }
}

void build_segment_tree(int32_t p, int32_t l, int32_t r)
{
    if (l == r) {
        segment_tree[p] = deviations[l];
        return;
    }

    int32_t m = (l + r) / 2;
    build_segment_tree(2 * p, l, m);
    build_segment_tree(2 * p + 1, m + 1, r);
    segment_tree[p] = std::min(segment_tree[2 * p], segment_tree[2 * p + 1]);
}

int32_t query_sparse_table(int32_t l, int32_t r)
{
    int32_t length = r - l + 1;
    int32_t k = 31 - __builtin_clz(length);

    if (l > r || k >= LOG_N) {
        return -1;
    }

    return std::min(sparse_table[l][k], sparse_table[r - (1 << k) + 1][k]);
}

int32_t query_segment_tree(int32_t p, int32_t l, int32_t r, int32_t i, int32_t j, int32_t d)
{
    int32_t maybe_result = query_sparse_table(i, j);

    if (maybe_result > d) {
        return maybe_result;
    }
    
    if (i > j) {
        return -1;
    }

    if (i == l && j == r) {
        if (segment_tree[p] > d) {
            return segment_tree[p];
        }
    }

    if (l == r) {
        return (segment_tree[p] > d) ? segment_tree[p] : -1;
    }

    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);
    return (ql != -1 && qr != -1) ? std::min(ql, qr) : std::max(ql, qr);
}

int32_t query_segment_tree(int32_t l, int32_t r, int32_t d)
{
    return query_segment_tree(1, 0, deviations.size() - 1, l, r, d);
}