Dynamic array supporting Range Minimum Queries

dynamic-RMQ

Dynamic array supporting Range Minimum Queries.

Data structure that represent a dynamic array supporting Range Minimum Queries. The data structure is built over an AVL tree [1] (code inspired by [1]). Each node stores its rank in the sub-array represented by its subtree, and the minimum value in the same sub-array.

Supported operations

In all operations rank is 0-based.

  • [](rank): Access the value in position rank in the array.
  • insert(rank, value): Inserts the value value before the element in position rank in the array.
  • update(rank, value): Updates the value in position rank in the array to value.
  • (left,right): Returns the value of the minimum in the interval [left,right) of the array.
  • to_vector(): Returns an std::vector containing the array.

Compile the test executable

git clone https://github.com/maxrossi91/dynamic-RMQ.git
cd dynamic-RMQ
mkdir build
cd build
cmake ..
make

Run the text executable

./test/avl_rmq_test

Linking to your progect using CMake and FetchContent

...

include(FetchContent)

## Add dynamic-RMQ
FetchContent_Declare(
  dynamic_rmq
  GIT_REPOSITORY https://github.com/maxrossi91/dynamic-RMQ.git
  )
  
FetchContent_GetProperties(dynamic_rmq)
if(NOT dynamic_rmq_POPULATED)
  FetchContent_Populate(dynamic_rmq)
  add_subdirectory(${dynamic_rmq_SOURCE_DIR} ${dynamic_rmq_BINARY_DIR} EXCLUDE_FROM_ALL)
endif()

...

add_executable(avl_rmq_test avl_rmq_test.cpp)
target_link_libraries(avl_rmq_test avl_rmq)

Usage

The class avl_rmq<typename K, typename S> has two template parameters determining the type to store the key, and the type to store the values. If you want to add satellite information to the tree, you can safely use std::pair<T1, T2> as value type, as long as the std::min() function is properly defined.

Example of usage

#include <iostream>
#include <avl_rmq.hpp>

int main(int argc, char *const argv[])
{


    int freq[] = {2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9};
    int n = sizeof(freq)/sizeof(freq[0]);

    // Instantiate the calss
    avl_rmq<int,int> avl;

    // Populate the avl_rmq
    for(size_t i = 0; i < n; ++i)
        avl.insert(i,freq[i]);

    avl.print(); // 2 1 1 3 2 3 4 5 6 7 8 9 

    std::cout << "Min in arr[1..3) is " << avl(1,3) << std::endl; // 1
    std::cout << "Min in arr[3..7) is " << avl(3,7) << std::endl; // 2

    avl.insert(0,12);
    avl.print(); // 12 2 1 1 3 2 3 4 5 6 7 8 9

    avl.update(3,12);
    avl.print(); // 12 2 12 1 3 2 3 4 5 6 7 8 9

    std::cout << "Min in arr[1..3) is " << avl(1,3) << std::endl; // 2
    std::cout << "Min in arr[6..12) is " << avl(6,12) << std::endl; // 3
    std::cout << "Value at arr[1] is " << avl[1] << std::endl; // 2

    return 0;
}

Caveat

At the moment the data structure does not supports deletions.

The data structure support only minimum queries, but can be easily adapted to supoprt also maximum queries.

Authors

Implementation:

References

[1] Adelson-Velskii, George M., and Evgenii Mikhailovich Landis. "An algorithm for organization of information." Doklady Akademii Nauk. Vol. 146. No. 2. Russian Academy of Sciences, 1962.

[2] AVL-tree in https://www.softwaretestinghelp.com/avl-trees-and-heap-data-structure-in-cpp/

Owner
Massimiliano Rossi
Postdoc at the University of Florida, in the Boucher Lab.
Massimiliano Rossi
Similar Resources

ZTE Nubia Z17 (codenamed "nx563j") is a high-range smartphone from Nubia.

ZTE Nubia Z17 (codenamed

ZTE Nubia Z17 (codenamed "nx563j") is a high-range smartphone from Nubia. It was released in June 2017.

Oct 25, 2021

Packages for simulating the Tethys-class Long-Range AUV (LRAUV) from the Monterey Bay Aquarium Research Institute (MBARI).

Packages for simulating the Tethys-class Long-Range AUV (LRAUV) from the Monterey Bay Aquarium Research Institute (MBARI).

LRAUV Simulation This repository contains packages for simulating the Tethys-class Long-Range AUV (LRAUV) from the Monterey Bay Aquarium Research Inst

Aug 3, 2022

Playbit System interface defines an OS-like computing platform which can be implemented on a wide range of hosts

PlaySys The Playbit System interface PlaySys defines an OS-like computing platform which can be implemented on a wide range of hosts like Linux, BSD,

Sep 12, 2022

A C++ concepts and range based character encoding and code point enumeration library

Travis CI (Linux:gcc) Text_view A C++ Concepts based character encoding and code point enumeration library. This project is the reference implementati

Sep 9, 2022

An experimental sprite rendering setup utilizing SSBO's, Threading, EnTT reactive systems, and array-textures based sprite caching.

entt-reactive An experimental sprite rendering setup utilizing pooled SSBO's, a multithreaded setup based on Even Todd's The Poor Man's Threading Arch

Apr 29, 2022

An associative array implemented by C laugnage

C Map An associative array implemented by C laugnage. This is an implementation of an associative array written by C. it is similar as C++ map but i

Jan 21, 2022

Tiny project to convert a .ase to a RGBA Byte array

Tiny project to convert a .ase to a RGBA Byte array

Apr 6, 2021

SX1276/77/78/79 Low Power Long Range Transceiver driver for esp-idf

SX1276/77/78/79 Low Power Long Range Transceiver driver for esp-idf

esp-idf-sx127x SX1276/77/78/79 Low Power Long Range Transceiver driver for esp-idf. I based on this. Changes from the original Added support for ESP32

Sep 5, 2022

SX1262//68 Low Power Long Range Transceiver driver for esp-idf

SX1262//68 Low Power Long Range Transceiver driver for esp-idf

esp-idf-sx126x SX1262//68 Low Power Long Range Transceiver driver for esp-idf. I ported from here. Ai-Thinker offers several LoRa modules. You can get

May 9, 2022
Display array is a board that sets 6 ST7735 display with a resolution of 80x160px in a linear array sharing the clock, data, rs, backlight pins together
Display array is a board that sets 6 ST7735 display with a resolution of 80x160px in a linear array sharing the clock, data, rs, backlight pins together

The display array is a board that sets 6 ST7735 display with a resolution of 80x160px in a linear array sharing the clock, data, rs, backlight pins together, and leaving individual access to the cs lines of each display, This board allows you to display images with a resolution of 480x160px.

Sep 15, 2022
Minimum Bait Cover Toolkit Syotti.

Minimum Bait Cover Toolkit Syotti This is a set of command line tools to compute a cover for a set of reference sequences using short bait strings.

Jul 21, 2022
Code for the paper Succinct k-mer Set Representations Using Subset Rank Queries on the Spectral Burrows-Wheeler Transform (SBWT)

SBWT This is the code for the paper Succinct k-mer Set Representations Using Subset Rank Queries on the Spectral Burrows-Wheeler Transform (SBWT). The

Jun 18, 2022
MDE is a model extraction tool that converts Destiny 2 dynamic models into fbx files supporting textures, skeletons, and all provided vertex data.

MDE is a model extraction tool that converts Destiny 2 dynamic models into fbx files. A dynamic model is one that is animated or is spawned in during the game.

Sep 2, 2022
An Arduino library which allows you to communicate seamlessly with the full range of u-blox GNSS modules
An Arduino library which allows you to communicate seamlessly with the full range of u-blox GNSS modules

u-blox makes some incredible GNSS receivers covering everything from low-cost, highly configurable modules such as the SAM-M8Q all the way up to the surveyor grade ZED-F9P with precision of the diameter of a dime.

Sep 13, 2022
J is an array programming language

J: From C to C++20 J is an array programming language created by Ken Iverson and Roger Hui (see image below).

Aug 20, 2022
Range library for C++14/17/20, basis for C++20's std::ranges

range-v3 Range library for C++14/17/20. This code was the basis of a formal proposal to add range support to the C++ standard library. That proposal e

Sep 21, 2022
Manual map shellcode (aka byte array) injector

ShellJector This little tool can download DLL from the internet and inject it as shellcode (aka byte array) into process with manual map injection. Th

Aug 31, 2022
An efficient, composable design pattern for range processing
An efficient, composable design pattern for range processing

Transrangers An efficient, composable design pattern for range processing. Intro Pull-based approach Push-based approach Transrangers Performance Tran

Apr 15, 2022
A C++ library with all the online array problems and etc which I get online

cpp-Library A C++ library with all the online array problems and etc which I get online. Setup To setup it simply just download the repo and then move

Dec 6, 2021