Disjoint Sparse Table applied to real-world scenarios. More...

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

Include dependency graph for disjoint_sparse_table_example.cc:

Classes
struct	Xor_Op

Functions
void	scenario_sales_analytics ()

void	scenario_probability ()

void	scenario_xor_checksum ()

void	scenario_construction ()

void	scenario_parlay_betting ()

int	main ()

Detailed Description

Disjoint Sparse Table applied to real-world scenarios.

This example demonstrates the Disjoint Sparse Table variants through realistic scenarios, highlighting the key advantage over the classical Sparse Table: support for non-idempotent associative operations like addition, multiplication, and XOR.

SCENARIO 1 — Sales Analytics (Sum_Disjoint_Sparse_Table — range sum)

A retail chain records daily revenue for each store across a quarter. After the quarter ends, the finance team needs to answer many queries of the form "what was the total revenue between day l and day r?" Because sum is associative but NOT idempotent (sum(a, a) = 2a != a), a classical Sparse Table cannot handle this. The Disjoint Sparse Table answers each query in O(1).

SCENARIO 2 — Probability Chains (Product_Disjoint_Sparse_Table)

A reliability engineer models a series system of n components. The probability that a subsystem spanning components [l, r] works is the product of individual reliabilities. Multiplication is associative but not idempotent, making the Disjoint Sparse Table ideal.

SCENARIO 3 — XOR Checksums (Gen_Disjoint_Sparse_Table — custom op)

A data integrity tool needs range-XOR queries on a block of data. XOR is associative and forms an abelian group. This scenario illustrates using a custom functor with the generic table.

SCENARIO 4 — Parlay Betting (Product_Disjoint_Sparse_Table)

A sportsbook offers a card of 12 consecutive match-ups. A bettor can build a "parlay" (accumulator) by picking any contiguous run of matches; the combined payout multiplier is the product of the individual decimal odds. Product is associative but NOT idempotent (odds * odds = odds² ≠ odds), so a classical Sparse Table cannot handle this, but the Disjoint Sparse Table answers every parlay combination in O(1).