AlgoScope

Segment Tree

structureadvancedTime O(log n)Space O(n)

A tree whose leaves are the array and whose every parent summarises its two children. Any range is covered by a few nodes, so a range question costs O(log n) instead of walking the range. Lazy propagation makes range updates as cheap as range queries: a node fully inside the update takes the whole change at once and keeps a tag saying its children still owe it, and the tag is only pushed one level down when a later operation needs to look below. Most of the work is deferred, and most of it is never done.

503070104060208

Build a sum tree over 8 values. The leaves are the array. Every parent holds the sum of its two children, so the root holds the sum of everything.

How it runs, step by step

  1. Build a sum tree over 8 values. The leaves are the array. Every parent holds the sum of its two children, so the root holds the sum of everything.

    Building a segment tree for range sum over 8 values.

  2. Node 7 covers indices 6 to 7. Its children hold 2 and 8, so it holds 10.

    Node 7 becomes 10.

  3. Node 6 covers indices 4 to 5. Its children hold 4 and 6, so it holds 10.

    Node 6 becomes 10.

  4. Node 5 covers indices 2 to 3. Its children hold 7 and 1, so it holds 8.

    Node 5 becomes 8.

  5. Node 4 covers indices 0 to 1. Its children hold 5 and 3, so it holds 8.

    Node 4 becomes 8.

  6. Node 3 covers indices 4 to 7. Its children hold 10 and 10, so it holds 20.

    Node 3 becomes 20.

  7. Node 2 covers indices 0 to 3. Its children hold 8 and 8, so it holds 16.

    Node 2 becomes 16.

  8. Node 1 covers indices 0 to 7. Its children hold 16 and 20, so it holds 36.

    Node 1 becomes 36.

  9. Built. 15 nodes for 8 values, and the root's 36 is the sum of the whole array. Any range can now be answered from O(log n) of these nodes.

    The segment tree is built. The root holds 36.

Remember

  • A node fully inside the query answers for its whole range at once. Only nodes on the edge split.
  • At most two nodes straddle the edge on each level, which is where O(log n) comes from.
  • An update is one root-to-leaf path recomputed on the way back up; a range update with lazy tags is O(log n) too, because a tag stands in for all the work below it.

Topics covered

Related

Where this is used

SecurityCertificate Transparency logs

A Certificate Transparency log is a Merkle tree over every certificate ever submitted: leaves are entries and each parent is the hash of its two children, which is this structure with hashing as the combine function. That shape is what keeps the proofs small: inclusion of one certificate is proved by the sibling node on each level of a single root-to-leaf path, and proving the old log is a prefix of the new one is a handful of subtree hashes covering the range of entries added since, the same few-nodes-cover-any-range argument. A client can check a log holding hundreds of millions of entries with a few dozen hashes.

Developer toolsEditor text buffers

The piece tree behind VS Code's text buffer keeps, in every node, the character count and the line-break count of its left subtree, which is the same summarise-your-children idea carried with two aggregates instead of one. Asking where line 40,000 starts then walks down the tree subtracting summaries, in O(log n), rather than scanning the file for newlines, and a keystroke only recomputes the counts along the path back to the root. Without those per-subtree counts, typing in a large file would cost time proportional to the file.

GraphicsArea of a union of rectangles

This is the problem the structure was invented for, by Jon Bentley in 1977. Sweep a vertical line across the plane and keep a segment tree over the y coordinates in which each node stores a cover count and how much of its range is covered by at least one rectangle; a rectangle adds its y interval at its left edge and removes it at its right, and the answer is read off the root after every event. Nothing is ever pushed down, because no subtree is read on its own and each remove undoes the same canonical nodes its add touched, so the counts cancel exactly. Changing only what each node stores turns the same sweep into the perimeter of the union, or the point where the most rectangles overlap at once.

BioinformaticsGenome interval indexes

The BAM and tabix indexes used by samtools cut a chromosome into a fixed hierarchy of bins, one of 512 Mb, then 8 of 64 Mb, then 64 of 8 Mb and so on down to 16 kb, and file each read in the smallest bin that fully contains it. The bins are nested ranges laid out like this tree's nodes, though the filing rule is the simpler one: a read goes into a single containing bin instead of being split across the canonical nodes a segment tree would use, which is why the spec calls the scheme an R-tree. A query for one region then only has to open the bins overlapping it on each of the six levels, so a viewer can jump into a 100 GB alignment file, pull back the reads over a single gene and touch almost nothing else.

Why it works this way

Why the node array is sized 4n and not 2n

The tree holds at most 2n - 1 nodes, but the heap numbering, children of i at 2i and 2i + 1, does not pack them when n is not a power of two: the bottom level is ragged and leaf indices scatter up to just under 4n. Sizing the array 2n and building recursively is a silent out-of-bounds write that only appears for certain n, which is why 4n is the usual reflex. Rounding n up to the next power of two makes the numbering dense, but the array is then twice the rounded size, so for an n just above a power of two it is still close to 4n. Laying the tree out iteratively from the leaves is the option that gives an exact 2n array.

The value returned for a node outside the range has to be a real identity

query returns IDENTITY for a node that does not overlap at all, and that value is fed straight into combine, so it must be the one that leaves the other operand unchanged: 0 for a sum tree, the largest possible int for min, 1 for a product. Returning 0 from a min tree is the bug everyone writes once, because the non-overlap branch fires on almost every partial query, so anything short of a whole-array query comes back 0 and nothing else looks broken. combine must also be associative, since the tree brackets a range the way the nodes happen to fall rather than left to right, which rules out subtraction and averaging; it does not have to be commutative, as long as the left child is always combined before the right.

Two kinds of lazy update have to collapse into a single tag

Range add on its own is easy, because two pending adds are just one bigger add. Put range assign in the same tree and the tags stop being interchangeable: an assign arriving at a node with a pending add has to throw that add away, while an add arriving at a pending assign has to fold into its value, so the node now needs a tag and a flag for which kind it is. The rule underneath is that a tag must be applicable to a whole node's aggregate in O(1) and any two tags must compose into one tag; when an operation cannot be expressed that way, lazy propagation does not apply to it. It is also why the sum version multiplies by hi - lo + 1 while a min version would just add v: the aggregate decides how the node's width enters.

When a Fenwick tree is the better answer

A Fenwick tree does point update and prefix sum in the same O(log n) with one array, a fraction of the code and far better constants, so for plain sums it wins outright. It gets there by subtracting one prefix from another, which needs the operation to have an inverse: min and max do not have one, and that is exactly where it stops. Range updates on their own are not the dividing line: for sums, two Fenwick trees together do range add and range sum. The segment tree earns its size when the operation cannot be undone, when a range update has to be applied under such an operation, or when a node has to carry more than one number, such as the best sub-range sum or a covered length.

Read more

Next up