A practical tutorial on segment trees for range queries

Many programming problems ask for information about a continuous part of an array: the sum of values between two indexes, the minimum temperature recorded over several days, or the maximum score in a match interval. If the array changes between queries, repeatedly scanning the requested range can become too slow.

A segment tree is a binary data structure for answering these range queries efficiently. It stores summaries of progressively smaller intervals, allowing a query to skip large portions of the input instead of visiting every element.

This technique is useful well beyond contest programming. A dashboard tracking Brisbane traffic, a Melbourne public transport timetable, or an ASX price monitor may repeatedly ask for aggregates over changing time windows. Segment trees provide a practical way to keep those calculations responsive.

Approach	Query time	Update time	Extra space	Best suited to
Direct range scan	O(n)	O(1)	O(1)	A few queries
Prefix sums	O(1)	O(n)	O(n)	Static range sums
Fenwick tree	O(log n)	O(log n)	O(n)	Dynamic sums
Segment tree	O(log n)	O(log n)	O(n)	Flexible range operations
Sparse table	O(1) for some operations	Not practical	O(n log n)	Static minimum or maximum

Why range queries need a data structure

Suppose an array contains daily electricity readings, and an application must answer the total from day left to day right. A direct loop checks every value in that interval. One query may be cheap, but thousands of overlapping queries can force the program towards O(nq) time, where n is the array length and q is the number of requests.

Prefix sums improve static range-sum queries. After building an auxiliary array, the sum from left to right can be calculated by subtracting two prefixes. However, changing one reading requires updating every later prefix, which costs O(n). This is unsuitable when data arrives continuously.

A segment tree stores an operation over each interval, such as a sum, minimum, maximum, greatest common divisor, or bitwise OR. Its design works when the operation can combine results from two adjacent subranges. For example, a sum for [left, right] is the sum of its left and right halves.

The same recursive partitioning appears in other algorithmic settings. It is conceptually different from the deliberately inefficient stooge sort, but both are useful reminders that an algorithm’s structure determines its performance.

How a segment tree stores intervals

The root represents the entire array. It splits into two children: one covers the left half and the other covers the right half. Each child splits again until a node represents a single element. These final nodes are called leaves.

For an array of eight values, the root covers [0, 7], its children cover [0, 3] and [4, 7], and the next level contains intervals such as [0, 1] and [2, 3]. The tree usually has O(n) nodes, even though the visual height is O(log n).

A convenient array representation uses a heap-style layout. If a node is stored at index i, its children are at 2 * i and 2 * i + 1. With one-based indexing, the root is at position 1. This avoids creating separate node objects and is usually fast in Python, C, and C++.

The stored value depends on the query. For range sums, each internal node stores the sum of its children. For a minimum query, it stores the smaller child value. The combination operation must be associative: grouping (a + b) + c and a + (b + c) must produce the same result.

Building and querying the tree

Building starts at the leaves and works upwards. If a node covers one array position, its value is copied directly from the input. Otherwise, the values of its two children are combined. Since every input value participates in a bounded number of combinations, construction takes O(n) time.

A query carries three intervals: the node’s interval, the requested interval, and the relationship between them. If the node lies completely outside the request, it contributes an identity value such as 0 for sums or positive infinity for minimum queries. If it lies completely inside, its stored summary is returned immediately.

When the intervals partially overlap, the query descends into both children and combines their results. At each level, only a limited number of boundary nodes are explored. The result is O(log n) for the usual segment-tree range query, rather than a scan of every requested item.

Useful query rules include:

Return the identity value for a completely disjoint interval.
Return the node’s aggregate for a completely covered interval.
Recurse into both children for partial overlap.
Combine child results with the selected operation.
Keep index conventions consistent, using either all-inclusive or half-open ranges.

Consider a sum query for [2, 6] on an array indexed from 0 to 7. The tree can accept complete blocks such as [2, 3] and [4, 5], then visit only the necessary part of [6, 7]. It never needs to inspect each item individually.

Updating values efficiently

A point update changes one array element. The corresponding leaf is replaced, then the algorithm walks back to the root, recalculating each ancestor from its updated children. The path length is proportional to the tree height, so the operation takes O(log n).

This is valuable for live data. A Melbourne sports application could update an AFL player’s score while answering queries for the highest score across a range of players. A Sydney transport service could update delay values while calculating totals over selected stops. The examples are different, yet both use the same point-update pattern.

A range update, such as adding five to every value in an interval, is more involved. Applying separate point updates would cost O(k log n) for k changed elements. Lazy propagation stores a pending operation at an internal node and delays pushing it to children until necessary, reducing many range-update and range-query combinations to O(log n).

Lazy propagation requires careful handling of pending values. For addition, a node can keep a deferred increment. For assignment, an assignment must replace older pending operations rather than being added to them. Bugs often arise when a query forgets to push a pending update before descending.

A Python implementation

The following implementation supports point updates and inclusive range-sum queries. The tree is allocated with four times the input length, a common safe bound for a recursive representation.

class SegmentTree:
    def __init__(self, values):
        self.n = len(values)
        self.tree = [0] * (4 * self.n)
        self.values = values
        if self.n:
            self._build(1, 0, self.n - 1)

    def _build(self, node, left, right):
        if left == right:
            self.tree[node] = self.values[left]
            return

        mid = (left + right) // 2
        self._build(node * 2, left, mid)
        self._build(node * 2 + 1, mid + 1, right)
        self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]

    def query(self, query_left, query_right):
        if not self.n or query_left > query_right:
            return 0
        return self._query(1, 0, self.n - 1, query_left, query_right)

    def _query(self, node, left, right, ql, qr):
        if qr < left or right < ql:
            return 0
        if ql <= left and right <= qr:
            return self.tree[node]

        mid = (left + right) // 2
        return (
            self._query(node * 2, left, mid, ql, qr)
            + self._query(node * 2 + 1, mid + 1, right, ql, qr)
        )

    def update(self, index, value):
        self._update(1, 0, self.n - 1, index, value)

    def _update(self, node, left, right, index, value):
        if left == right:
            self.tree[node] = value
            return

        mid = (left + right) // 2
        if index <= mid:
            self._update(node * 2, left, mid, index, value)
        else:
            self._update(node * 2 + 1, mid + 1, right, index, value)

        self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]

For an input such as [4, 7, 1, 9, 2], query(1, 3) returns 17, because it combines 7, 1, and 9. Calling update(2, 10) changes the array to [4, 7, 10, 9, 2]; the same query then returns 26.

In production code, validate indexes and decide how an empty input should behave. Python recursion is normally safe for a logarithmic tree, though an iterative segment tree can avoid recursion entirely. When processing data imported with Pandas and Arrow pipeline, convert values and indexes into a predictable form before building the structure.

Choosing the right tool in practice

A segment tree is powerful, but it is not automatically the best choice. Prefix sums are simpler for an immutable array of totals. A Fenwick tree uses less memory and is often easier to implement when the operation is limited to cumulative sums. Sparse tables are excellent for static minimum or maximum queries because they can answer them in O(1) after preprocessing.

For machine-learning feature preparation, a segment tree may help maintain rolling statistics over a changing stream, while a batch-oriented data structure is often better for a fixed dataset. The correct choice depends on update frequency, operation type, memory limits, and whether queries are online.

A useful decision guide is:

Use prefix sums when values never change and range sums dominate.
Use a Fenwick tree for dynamic point updates and prefix or range sums.
Use a segment tree for several aggregate operations or more complex combinations.
Use lazy propagation for frequent interval updates.
Use a sparse table for static idempotent operations such as minimum or maximum.

The operation can be customised by replacing addition and its identity value. A minimum tree uses min(left_result, right_result) and positive infinity for disjoint ranges. A maximum tree uses max and negative infinity. This same flexibility makes segment trees a valuable foundation for more advanced competitive-programming techniques.

A tree can also support richer records. Each node might store both a sum and a maximum, or the best prefix and suffix values needed for a maximum-subarray query. The combination function then becomes a small, well-defined piece of logic. This pattern resembles the composable thinking used in ensemble methods such as the random forest explanation: useful results emerge by combining summaries according to precise rules.

For Australian applications, data governance still matters alongside algorithmic speed. If a system stores identifiable customer or travel information, the Australian Privacy Act 1988 and its Australian Privacy Principles may affect collection, retention, and access controls. A fast range-query engine should therefore receive only the data it needs, with sensitive fields separated or removed before indexing.