cartesian_tree_example.cc File Reference

Four creative scenarios demonstrating Cartesian Tree, LCA, and RMQ. More...

#include <tpl_cartesian_tree.H>
#include <tpl_sparse_table.H>
#include <iostream>
#include <iomanip>
#include <chrono>
#include <random>
#include <vector>

Include dependency graph for cartesian_tree_example.cc:

Go to the source code of this file.

Functions
static void	scenario_1 ()
static void	scenario_2 ()
static void	scenario_3 ()
static void	scenario_4 ()
int	main ()

Detailed Description

Four creative scenarios demonstrating Cartesian Tree, LCA, and RMQ.

SCENARIO 1 — "El Arbol Genealogico de los Datos"

Visualizes the Cartesian Tree as a hierarchy: given an array of ages, build the tree and show parent/children. Demonstrates heap property

• inorder = original array.

SCENARIO 2 — "Ancestros Comunes en el Linaje"

Uses Euler_Tour_LCA to find common ancestors. Visualizes the Euler Tour and depths.

SCENARIO 3 — "RMQ sin Trucos: de Arbol a Respuestas O(1)"

Builds Cartesian_Tree_RMQ and compares results with Sparse_Table on the same data. Shows the chain CT -> Euler Tour -> Sparse Table -> O(1).

SCENARIO 4 — "El Circulo Completo: RMQ <-> LCA"

Demonstrates the equivalence: RMQ(l,r) = value at LCA(l,r). Comparative timing of build/query vs Sparse Table.

Definition in file cartesian_tree_example.cc.

Function Documentation

main()

int main

(

)

Definition at line 319 of file cartesian_tree_example.cc.

References scenario_1(), scenario_2(), scenario_3(), and scenario_4().

scenario_1()

static void scenario_1 ( )

static

Definition at line 73 of file cartesian_tree_example.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Cartesian_Tree< T, Comp >::root().

Referenced by main().

scenario_2()

static void scenario_2 ( )

static

Definition at line 130 of file cartesian_tree_example.cc.

References Aleph::Gen_Cartesian_Tree< T, Comp >::data_at(), Aleph::Gen_Euler_Tour_LCA< T, Comp >::depth_of(), Aleph::Gen_Euler_Tour_LCA< T, Comp >::distance(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Euler_Tour_LCA< T, Comp >::euler_tour(), Aleph::Gen_Euler_Tour_LCA< T, Comp >::euler_tour_size(), Aleph::Gen_Euler_Tour_LCA< T, Comp >::lca(), Aleph::Gen_Euler_Tour_LCA< T, Comp >::size(), and Aleph::Gen_Euler_Tour_LCA< T, Comp >::tree().

Referenced by main().

scenario_3()

static void scenario_3 ( )

static

Definition at line 176 of file cartesian_tree_example.cc.

References Aleph::divide_and_conquer_partition_dp(), l, r, and Aleph::range().

Referenced by main().

scenario_4()

static void scenario_4 ( )

static

Definition at line 225 of file cartesian_tree_example.cc.

References Aleph::divide_and_conquer_partition_dp(), l, N, r, and rng.

Referenced by main().