Segment tree visualizer

Type or paste your array and press Build tree. Choose whether nodes store the sum, minimum or maximum, and whether your exercise counts indexes from 0 or 1. Then run range queries, point updates or lazy range additions. Each operation is listed on the right; click one to see the tree as it was right after it, with the nodes it visited coloured and every step explained.

• Each node shows its range on top and its value below; the small number at its corner is its position in the tree array (root 1, children 2i and 2i + 1).
• Copy answer gives the built tree and every operation's steps as text; Copy link saves the array and all operations.

A segment tree answers questions about ranges of an array, such as the sum or minimum of elements l to r, while still allowing the array to change. Summing the range directly takes time proportional to its length; keeping prefix sums answers in constant time but makes every update cost O(n). A segment tree makes both queries and updates O(log n).

It is a binary tree in which each node covers a range of the array and stores the answer for it. The root covers the whole array; each node's two children cover its left and right halves; the leaves are the single elements. Any range can then be assembled from O(log n) nodes whose ranges fit inside it.

Building is a recursion: a node covering [l, r] with l = r is a leaf holding a[l]; otherwise it splits at m = ⌊(l + r)/2⌋, builds both children and combines their values. Every node is built once, so the cost is O(n). For the array 5, 8, 6, 3, 2, 7, 2, 6 with sums, the tree is:

A query for [l, r] starts at the root and, at each node, does one of three things. If the node's range lies entirely inside [l, r], it returns the stored value without going further. If it lies entirely outside, it returns nothing (0 for a sum, +∞ for a minimum). Otherwise it asks both children and combines their answers.

On the example array, the sum of [2, 6] is 20. The query visits 9 nodes, takes its answer from the whole nodes [2, 3], [4, 5], [6, 6], and skips 2 that lie outside. At most four nodes are visited on any level, so a query is O(log n). Across 24,024 sampled ranges of a 1,000-element array, whose tree has 11 levels, the most nodes any query visited was 39, and the average 32.8.

Changing a[i] affects exactly the nodes whose ranges contain i: one per level, along the path from the root to the leaf. The update walks down that path, changes the leaf and recomputes each node on the way back up from its two children. That is O(log n) nodes, against O(n) for rebuilding prefix sums.

Adding a value to every element of a range one by one would cost O(n log n). With lazy propagation, a range update visits the same nodes a query would. At a node whose range lies entirely inside the update, it changes the node's value (by v times the range length for a sum, by v for a minimum or maximum) and records "+v pending" for its children instead of visiting them. The pending value is pushed one level down only when a later operation has to go below that node.

On the example array, adding 3 to [1, 6] visits 11 nodes and leaves pending additions on [2, 3] and [4, 5]. A later query for the single element [2, 2] has to go below one of those nodes, pushes 1 pending addition down on the way, and returns 9, which is 6 + 3.

• 0-based or 1-based indexes. Competitive programming code is usually 0-based; many textbooks number elements from 1. The switch above changes how ranges are read and shown, not the tree.
• Node numbering. With the root at 1, children are 2i and 2i + 1; with the root at 0, they are 2i + 1 and 2i + 2.
• Where the split falls. Splitting [l, r] at ⌊(l + r)/2⌋ gives the left child the extra element when the length is odd, as here. Iterative bottom-up implementations lay the tree out differently and visit different nodes, though they return the same answers.
• Inclusive or half-open ranges. This page uses [l, r] with both ends included; some code uses [l, r).