Let's look at the complexities of the <preprocess, query, update an element> operations. Let's denote n the size of the initial array and q the number of queries.
- Sparse table
<O(nlogn) , O(q) , O(nlogn)> - Segment tree
<O(n) , O(qlogn) , O(logn) >
It seems to me that even if we consider an application where there is no need to do updates (I'm not even talking about range updates), a sparse table is almost always worse except in the case where q >> n (going from an overall complexity (preprocessing + querying) of qlogn to q thanks to the sparse table since nlogn and n are negligible in that scenario), but then a dynamic programming in O(n²) might even work better.
I'm therefore interested in any real-world or, if there is none/too few, made up/edge cases where sparse tables are useful.
