As a competitive programmer (IOI gold medalist / ICPC world finalist), segment trees are really the most classic and versatile data structure seen in competitiv

As a competitive programmer (IOI gold medalist / ICPC world finalist), segment trees are really the most classic and versatile data structure seen in competitive programming. In addition to the basic idea, there are problems that can be solved with all sorts of different variations - segment trees with lazy propagation, sparsity, persistence, Li-Chao queries, 2D queries, etc. There's an extremely optimized, 10-line, iterative C++ implementation of the basic data structure due to Oleksandr Bacherikov. https://codeforces.com/blog/entry/18051 https://codeforces.com/blog/entry/18051 Also see Fenwick trees: logarithmic-time range queries in 3 lines of C code. https://en.wikipedia.org/wiki/Fenwick_tree https://en.wikipedia.org/wiki/Fenwick_tree