src/util/range_minimum_query.h

/*
 * Copyright 2025 Valve Corporation
 * SPDX-License-Identifier: MIT
 */

#ifndef RANGE_MINIMUM_QUERY_H
#define RANGE_MINIMUM_QUERY_H

#include <stdint.h>
#include <string.h>

#ifdef __cplusplus
extern "C" {
#endif

/**
 * Find the smallest integer in a portion of an array.
 *
 * We use the simple RMQ algorithm that uses O(n log n) preprcessing time and
 * O(1) query time (see eg. Bender and Colton section 3).
 *
 * Bender, M.A., Farach-Colton, M. (2000). The LCA Problem Revisited. In:
 *     Gonnet, G.H., Viola, A. (eds) LATIN 2000: Theoretical Informatics. LATIN
 *     2000. Lecture Notes in Computer Science, vol 1776. Springer, Berlin,
 *     Heidelberg. https://doi.org/10.1007/10719839_9
 */

struct range_minimum_query_table {
   uint32_t *table;
   uint32_t width, height;
};

static inline void
range_minimum_query_table_init(struct range_minimum_query_table *table)
{
   memset((void*) table, 0, sizeof(*table));
}

void
range_minimum_query_table_resize(struct range_minimum_query_table *table,
                                 void *mem_ctx, uint32_t width);

/**
 * Perform preprocessing on the table to ready it for queries.
 *
 * Takes O(n log n) time.
 */
void
range_minimum_query_table_preprocess(struct range_minimum_query_table *table);

/**
 * Find the smallest value in the array among indices in the half-open interval
 * [left_idx, right_idx).
 *
 * Takes O(1) time.
 */
uint32_t
range_minimum_query(struct range_minimum_query_table *const table,
                    uint32_t left_idx, uint32_t right_idx);

#ifdef __cplusplus
}
#endif

#endif