Efficient RMQ algorithm above constant value

Question

I am trying to solve some range minimum query where the minima must be above some constant.

Problem:
Given some positive integers a₁, ... a_N. For each query of integers l, r, d find the minimal element that is still greater than d, that is find min{a_i | l <= i <= r, a_i > d}.

I already tried the segment tree algorithm with an additional sparse table to speed up the queries when all elements are above d. This gave me an complexity of O(N * log(N) + Q * log(N)). Using the sparse table did not improve the complexity, but it pruned a lot of the calls for the segment tree query.

However, this algorithm is still too slow. Does anybody has a faster algorithm that I could try?

Edit:

People are pointing out that it has to do with my implementation and that I am using the correct data structure. So here is my code, maybe I did something wrong that increased the complexity:

#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);
}

This is the same as this question, but it didn't had any answer: https://stackoverflow.com/questions/48167547/range-minimum-query-above-a-constant-value — Yeladia, Jan 14 '23 at 15:12
Sounds like you are using the right data structure… is it an implementation optimization issue? How big is N? What does the data look like? — wcochran, Jan 14 '23 at 15:21
If you are using C++ is look like boost has tools for this. See answer here https://stackoverflow.com/questions/28535296/stl-for-segment-tree-in-c — wcochran, Jan 14 '23 at 15:26
Maybe I need more coffee, but I don't see how `query_segment_tree` runs in log time in the worst case. I'll post another approach. — David Eisenstat, Jan 14 '23 at 15:34

score 0 · Answer 1 · answered Jan 14 '23 at 15:40

Here’s another approach, that runs in linearithmic time.

We sweep a quantity x from −∞ to ∞. Whenever x = d for some query, we insert [ℓ, r] into an interval tree. Whenever x = a_i for some i, we delete all of the intervals that contain i, reporting i as their result. We resolve nondeterminism by doing the latter before the former.

The cost is sorting the array, sorting the intervals by d, merging them into an event array, and performing an amortized logarithmic time operation for each one.

Took some time, but I understand it now. ^^ Thank you. – Yeladia Jan 14 '23 at 15:58 — Yeladia, Jan 14 '23 at 15:58

Efficient RMQ algorithm above constant value

1 Answers1