1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
/*
* 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
|
