A segment tree is a data structure that stores summaries of contiguous pieces of an indexed array in a binary tree. It can answer a range query and replace an individual value in time per operation when summaries combine in constant time. A market-data service can use one to answer “what was the lowest bar low between these two times?” even after a vendor corrects an earlier bar.
Query the blocks that fit
Start with one leaf per observation, ordered by time. The root covers the whole array, and each internal node splits its range at the midpoint and stores the minimum of its two children. Write for a zero-based, half-open range. It includes index , excludes , and has entries. Adjacent ranges can therefore share a boundary without sharing an observation.
Suppose six consecutive bar lows in a fictional series are USD. To query , ignore disjoint nodes, take the stored minimum of each node fully inside the query, and split any partially overlapping node. In the tree below, the selected ranges are , and . They cover indices 1 through 4 exactly once. Their stored minima give USD. University of Illinois, Segment Trees, range-minimum queries.
![For six fictional bar lows, query [1, 5) uses nodes [1, 3), [3, 4) and 4, 5). Correcting index 4 from 2 to 6 USD changes its leaf and three ancestors, lifting the query minimum from 2 to 3 USD.
Outlined blocks supply the query result. The dashed path shows which nodes the point assignment recomputes.
Replace one low
Suppose the feed corrects index 4 from 2 to 6 USD. Replace that leaf and walk back to the root. The parent now stores , its parent stores , and the root stores . The original query reads the same three blocks and now gives USD. Recomputing from both children matters when the old minimum rises. The sibling of an updated node can supply the new minimum for their parent.
A point assignment recomputes one path. In a range query, at most two nodes at each depth partially overlap the requested interval and need to be split. This gives the worst-case bounds. Construction takes time and storage because each leaf and internal node needs one summary. The example assumes a fixed, sorted timestamp-to-index mapping and valid bar lows. In a historical replay, apply the correction when it became available to avoid look-ahead bias. The SelfMadeQuant lesson Tabular and Time-Indexed Data explains how to validate a time index and choose the aggregation for each price or volume field. The preview is public and the full lesson requires membership.
What the summaries must support
The merge must be associative so changing the grouping of consecutive blocks preserves the result. It can be order-sensitive as long as blocks are merged from left to right. An identity gives a neutral summary for empty ranges or unused leaves in a padded tree. For finite lows, is the identity because . It represents an empty contribution, so a missing market observation still needs its own data policy. For range totals with point changes, a Fenwick tree can obtain an interval total by subtracting prefix sums. Minima have no corresponding subtraction rule. AtCoder Library, Segtree.
A lazy segment tree can also handle compatible updates to whole ranges. When an update fully covers a node, it updates the stored summary and leaves a pending operation to pass to its children before descending. Adding a constant to every low in a covered block shifts the block minimum by the same constant. Adding a constant to every element of a sum block needs the block length as well as the old sum. The update must act directly on the stored summary, agree with merging separately updated children, and let successive pending operations compose in time order. The logarithmic bound assumes that applying and composing those operations take constant time. AtCoder Library, Lazy Segtree.
Sources
- Mattox Beckman, University of Illinois, Segment Trees. Tree construction, range decomposition and point updates.
- AtCoder Library, Segtree. Associative merges, identities, half-open ranges and complexity.
- AtCoder Library, Lazy Segtree. Range updates, composition and compatibility with merging.