sparse_table_example.cc File Reference

Sparse Table applied to competitive programming and sensor analysis. More...

#include <cstdio>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <tpl_sparse_table.H>

Include dependency graph for sparse_table_example.cc:

Go to the source code of this file.

Functions
static void	scenario_sensor_monitoring ()
static void	scenario_sports_leaderboard ()
static void	scenario_range_gcd ()
static void	scenario_construction ()
int	main ()

Detailed Description

Sparse Table applied to competitive programming and sensor analysis.

This example demonstrates the three Sparse Table variants through realistic scenarios.

SCENARIO 1 — Sensor Monitoring (Sparse_Table — range minimum)

An industrial plant has a row of temperature sensors sampled once per second. After the sampling window closes, operations needs to answer many queries of the form "what was the coldest reading between second l and second r?" The data is static (the window is already closed), so a Sparse Table gives O(1) per query after an O(n log n) build.

SCENARIO 2 — Sports Leaderboard (Max_Sparse_Table — range maximum)

A swimming competition records lap times for each swimmer. The commentator wants to quickly find the best (fastest) lap in any contiguous block of laps. Since lower time = better, we actually want range minimum on times; but to showcase Max_Sparse_Table we track scores (higher = better) assigned by judges.

SCENARIO 3 — GCD Queries (Gen_Sparse_Table — custom idempotent op)

A number-theory teaching tool: given a sequence of integers, answer range-GCD queries in O(1). GCD is idempotent (gcd(a, a) = a), so it fits the Sparse Table perfectly.

COMPILE & RUN:

g++ -std=c++20 -I.. -o sparse_table_example sparse_table_example.cc ./sparse_table_example

Definition in file sparse_table_example.cc.

Function Documentation

main()

int main

(

)

Definition at line 313 of file sparse_table_example.cc.

References Aleph::maps(), scenario_construction(), scenario_range_gcd(), scenario_sensor_monitoring(), and scenario_sports_leaderboard().

scenario_construction()

static void scenario_construction ( )

static

Definition at line 271 of file sparse_table_example.cc.

References Aleph::maps(), and Aleph::HTList::size().

Referenced by main().

scenario_range_gcd()

static void scenario_range_gcd ( )

static

Definition at line 213 of file sparse_table_example.cc.

References Aleph::Gen_Sparse_Table< T, Op >::get(), l, Aleph::maps(), Aleph::Gen_Sparse_Table< T, Op >::num_levels(), Gcd_Op::operator()(), Aleph::Gen_Sparse_Table< T, Op >::query(), and Aleph::Gen_Sparse_Table< T, Op >::size().

Referenced by main().

scenario_sensor_monitoring()

static void scenario_sensor_monitoring ( )

static

Definition at line 87 of file sparse_table_example.cc.

References brute_min(), Aleph::DynList< T >::get(), l, Aleph::maps(), min(), and Aleph::HTList::size().

Referenced by main().

scenario_sports_leaderboard()

static void scenario_sports_leaderboard ( )

static

Definition at line 151 of file sparse_table_example.cc.

References Aleph::DynList< T >::get(), l, Aleph::maps(), and Aleph::HTList::size().

Referenced by main().