Concepts48
Category
Iterative Segment Tree
An iterative segment tree stores all leaves in tree[n..2n-1] and internal nodes in tree[1..n-1], enabling O(\log n) point updates and range queries without recursion.
Segment Tree Beats
Segment Tree Beats is a segment tree variant that supports range chmin/chmax (clamping) together with queries like range sum, min, and max in amortized logarithmic time.
Binary Trie for XOR
A binary trie (also called a bitwise trie) stores numbers by their binary bits, branching on 0/1 at each level.
Segment Tree - Handling Multiple Lazy Operations
When a segment tree supports multiple range updates, you must define how lazy tags compose, because the order of operations matters and composition is not commutative.
Segment Tree with Lazy Propagation
A segment tree with lazy propagation supports fast range updates and range queries in O(\log n) time.
Dynamic Segment Tree
A dynamic segment tree stores values over a huge coordinate range by creating nodes only when an operation touches their interval.
Trie (Prefix Tree)
A trie (prefix tree) stores strings or bit-sequences so that common prefixes share nodes, making operations depend on the key length L rather than the set size.
Segment Tree Basics
A segment tree is a complete binary tree that stores information about array intervals to answer range queries and support point updates in O(log n).
2D Fenwick Tree
A 2D Fenwick Tree (Binary Indexed Tree) supports point updates and rectangle sum queries in O(log n × log m) time.
Fenwick Tree - Range Update Range Query
A Fenwick Tree (Binary Indexed Tree) can support range additions and range sum queries by maintaining two trees, often called B1 and B2.
Fenwick Tree (Binary Indexed Tree)
A Fenwick Tree (Binary Indexed Tree) maintains prefix sums so you can update a single position and query a prefix in O(\log n) time with a tiny constant factor.
Sparse Table
A Sparse Table is a static range-query data structure that preprocesses an array in O(n \log n) time and answers many queries in O(1) time.