Advanced Trees Checkpoint

1. Segment tree range queries and point updates run in:

O(log n) O(n) O(1) O(n log n)

2. Sparse tables give O(1) queries for operations that are:

Idempotent (min/max/gcd) Non-associative Order-dependent only Randomized

3. For a query length L, sparse table uses k = floor(log2(L)).

4. Interval trees prune search using the subtree's:

Maximum end value Minimum start value Node depth Heap size