Static range query algorithms
Square root decomposition with sorted blocks for range counting queries and point updates in O(sqrt n).
Static range query structure — O(1) for idempotent operations (min/max/gcd), O(log n) for non-idempotent.
Nested segment tree for 2D point update and rectangle queries in O(log n * log m).
Classic segment tree with point update and range query for any associative operation.
2D prefix sum for O(1) rectangle sum queries on a static grid.
Segment tree preserving all versions via path copying — O(log n) per update, O(n + q log n) total memory.
2D difference array for O(1) range updates and O(n*m) final propagation.
Mo's algorithm adapted for tree path queries using Euler tour flattening and LCA via binary lifting.
Offline range query processing with Hilbert curve ordering for optimal cache performance.
Segment tree with lazy propagation — supports range updates and range queries in O(log n).
Fenwick tree supporting both range add and range sum queries using two BITs.
2D Binary Indexed Tree for point updates and rectangle sum queries in O(log n * log m).
Binary Indexed Tree for prefix sum queries and point updates in O(log n).