UPDATE(node,lo,hi,idx,val): path update, propagate up
Section 2 -- The Idea, Step by Step
Start here (the everyday picture). Picture a long row of jars on a shelf, each holding some coins. A friend keeps asking, "How many coins total in jars 3 through 47?" and every so often drops a coin into one jar. The obvious way is to open every jar in the range and add them up. That is fine once, but painful if they ask a thousand times. A segment tree is a cheat sheet that pre-adds groups of jars, so you almost never count from scratch.
Build it up (high-school view). Split the row in half, then each half in half again, all the way down to single jars. Every group remembers its own total. Now a question about jars 3–47 is answered by stitching together a handful of group-totals instead of opening every jar. With $n$ jars these groups stack into about $\log_2 n$ layers, so a million jars are only about 20 layers deep. A single range query touches at most about 4 groups per layer, so roughly $4\times 20 \approx 80$ stored totals, not a million openings. That is the whole payoff: $O(n)$ work becomes $O(\log n)$.
Make it precise (AP / intro-college). Formally it is a balanced binary tree over array indices. The root covers $[0,\,n-1]$; a node covering $[lo,\,hi]$ splits at $mid=\lfloor (lo+hi)/2\rfloor$ into children $[lo,\,mid]$ and $[mid+1,\,hi]$, and stores the aggregate of its range under any associative operation that has an identity — sum (identity $0$), min ($+\infty$), max ($-\infty$), gcd ($0$), or xor ($0$). A range query recurses with three cases: no overlap (return the identity and prune that whole subtree), total overlap (return the stored value), and partial overlap (recurse into both children). At most two nodes per level partially overlap, so at most four are visited per level — hence $O(\log n)$. A point update walks one root-to-leaf path and refreshes each parent on the way back up, also $O(\log n)$. For whole-range updates, lazy propagation stamps a pending change on a covering node and pushes it down to children only when a later visit needs them, keeping range updates at $O(\log n)$ instead of $O(n)$.
Try this in the sim above. (1) Drag the n slider to its maximum and press Play — watch the Comparisons counter climb and notice it grows far slower than $n^2$ as the structure gets bigger. (2) Switch the preset between Sorted and Reverse and compare the Comparisons counter: a segment tree's cost depends on the range geometry of your queries, not on whether the data happens to be sorted. (3) Press Next repeatedly and follow the highlighted lines in the pseudo-code panel to trace how BUILD keeps splitting each range in half until it reaches single-element leaves.
Section 3 -- Complexity Analysis
Symbol
Meaning
n
Input size
T(n)
Time complexity function
h
Height or depth of structure
k
Key or rank parameter
W(n)
Worst-case complexity
A(n)
Average-case complexity
Step 1 -- Structure. Segment tree is a full binary tree. Root represents range [0,n-1]. Each node stores aggregate (sum, min, max) of its range. Left child: [lo, mid], right child: [mid+1, hi]. Total nodes: at most 4n. Array size: 4*n.
Step 3 -- QUERY O(log n). Three cases: no overlap (return identity), total overlap (return node value), partial overlap (recurse both children). At most 4 nodes visited per level. O(log n) levels. Total: O(4 log n) = O(log n).
Step 4 -- POINT UPDATE O(log n). Update leaf, propagate changes up to root. Path length = height = O(log n).
Step 5 -- RANGE UPDATE with Lazy Propagation O(log n). Without lazy: update each element separately O(n). With lazy: mark nodes for deferred update ('lazy' flag). Propagate laziness down only when needed. Range update: O(log n). Lazy propagation also enables range min/max updates.
Step 6 -- Space O(n). 4*n array. Each node stores one aggregate value. Lazy propagation adds one more array: 4*n lazy values. Total: O(n) space.
Section 4 -- FAQ
What problems does a segment tree solve? concept+
Any problem requiring: repeated range aggregate queries (sum, min, max, GCD) AND point or range updates on an array. Without segment tree: query O(n), update O(1). With: both O(log n). Used for competitive programming, databases, and computational geometry.
What is lazy propagation? concept+
When updating a range [l,r], instead of updating all nodes, mark the range node as 'lazy' (needs update). When a future query or update visits a lazy node, first push the lazy update to children, then proceed. Avoids O(n) per range update.
When to use segment tree vs BIT (Fenwick tree)? applied+
Segment tree: supports any associative operation (sum, min, max, GCD), range updates. BIT: only prefix-sum type queries, simpler code, faster constant. For sum queries only: prefer BIT. For min/max or range updates: segment tree.
Why allocate 4*n nodes? complex+
Height = ceil(log2(n))+1. Total nodes <= 2^(height+1)-1. For n not a power of 2, the tree may have up to 4n-5 nodes. Safe bound: 4*n. Alternatively, use 2 * next_power_of_2(n).
What is the query algorithm's 3-case logic? nonobv+
No overlap [l,r] and [lo,hi] disjoint: return identity (0 for sum, INF for min). Total overlap [lo,hi] inside [l,r]: return stored value (full answer for this segment). Partial overlap: split and recurse. At most 2 nodes per level partially overlap (one near each end of [l,r]); together with the fully-covered children they hand off to, at most 4 nodes are visited per level, giving O(log n).
Can segment trees handle 2D range queries? deep+
Yes -- 2D segment tree (segment tree of segment trees). For n*n grid: O(n^2) space, O(log^2 n) query. Merge sort tree (sorted lists in nodes) enables range-kth queries in O(log^2 n). Fractional cascading reduces to O(log n).
Section 5 -- Common Misconceptions
Conceptual Misconceptions
X Segment tree requires O(n log n) space.
O Space is O(4n) = O(n). Each level has at most n nodes (leaves), and internal nodes are fewer. 4n is a safe upper bound.
X Query always recurses into both children.
O Query only recurses into a child if its range overlaps with [l,r]. No-overlap subtrees are pruned immediately, giving O(log n) total.
X Segment tree only works for sum queries.
O Segment tree works for any associative operation with identity: sum, min, max, product, GCD, XOR, matrix multiplication, etc.
Implementation Errors
X Allocating 2*n nodes instead of 4*n.
O For n not a power of 2, internal node indices exceed 2*n. Always allocate 4*n to be safe, or explicitly pad to next power of 2.
X Forgetting identity value in no-overlap case.
O Must return proper identity: 0 for sum, INT_MAX for min, INT_MIN for max, 1 for product. Returning 0 for min queries gives wrong results.
X Forgetting to push lazy values down before recursing.
O In lazy propagation: always propagate lazy to children BEFORE recursing or reading their values. Not doing so returns stale values.