Building & Querying Segment Trees

March 2026 · 22 min read

In the introduction, we learned what a segment tree is and why it exists. Now we'll see exactly how it's built and how range queries work, with full code, step-by-step traces, and interactive animations.

Building the Segment Tree

The Idea

Building a segment tree is a classic divide and conquer algorithm:

1. Base case: If the range has one element (start == end), it's a leaf. Store the array value directly.
2. Recursive case: Split the range at mid = (start + end) / 2. Recursively build the left child for [start, mid] and the right child for [mid+1, end]. Then set this node's value to left + right (merge).

The recursion naturally produces a bottom-up construction: leaves are filled first, then their parents, all the way up to the root.

The Pseudocode

Why 2*node and 2*node+1?

This is the same indexing scheme as a binary heap. If the current node is at index node in the array:

• Left child: 2 * node
• Right child: 2 * node + 1

Starting from node 1 (root), the entire tree maps cleanly into a flat array. No pointers needed.

Walkthrough: Building for [1, 3, 5, 7]

Let's trace every recursive call:

Build Complexity

Time: O(n), Each of the 2n-1 nodes is visited exactly once. The merge at each internal node is O(1). Total: O(n).

Space: O(4n) for the tree array. O(log n) for the recursion stack.

C++ Implementation: Build

void build(const vector<int>& arr, vector<int>& tree,
           int node, int start, int end) {
    if (start == end) {
        // Leaf node: store the array element
        tree[node] = arr[start];
        return;
    }
    int mid = (start + end) / 2;

    // Recursively build children
    build(arr, tree, 2 * node,     start, mid);
    build(arr, tree, 2 * node + 1, mid + 1, end);

    // Internal node: merge children
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

// Usage:
// vector<int> arr = {1, 3, 5, 7};
// vector<int> tree(4 * arr.size(), 0);
// build(arr, tree, 1, 0, arr.size() - 1);

Range Queries

Now the powerful part. Given the built tree, we want to compute sum(l, r) in O(log n).

The Three Cases

At each recursive call, we're at a node that covers range [start, end] and we want the sum of [l, r]. There are exactly three possibilities:

Case 1: Total Overlap (the range is fully inside the query)

If l ≤ start AND end ≤ r, then the node's entire range is inside our query range. Return the node's value directly. No need to recurse further, this is the "shortcut" that makes segment trees fast.

Case 2: No Overlap (the range is completely outside the query)

If start > r OR end < l, there's zero overlap. Return the identity element (0 for sum, ∞ for min, −∞ for max). This entire subtree is irrelevant.

Case 3: Partial Overlap

The node's range straddles the query boundary. We can't use this node's value directly because it covers elements we don't want. Recurse into both children and merge the results.

The Pseudocode

Walkthrough: query(1, 3) on [1, 3, 5, 7]

We want the sum of arr[1] + arr[2] + arr[3] = 3 + 5 + 7 = 15.

We visited only 5 nodes (out of 7 total). Node 6 and 7 were never touched because their parent (node 3) was a total overlap. In larger trees, this pruning saves enormous amounts of work.

A Harder Example: query(2, 5) on [1, 3, 5, 7, 9, 11, 2, 4]

This example uses the larger 8-element array. The query wants sum of arr[2..5] = 5 + 7 + 9 + 11 = 32.

Only 7 nodes visited. Nodes 5 and 6 provided the answer directly, their children were never touched. The no-overlap branches (4 and 7) were pruned instantly.

C++ Implementation: Query

int query(const vector<int>& tree, int node,
          int start, int end, int l, int r) {
    // Case 2: No overlap
    if (r < start || end < l)
        return 0;

    // Case 1: Total overlap
    if (l <= start && end <= r)
        return tree[node];

    // Case 3: Partial overlap
    int mid = (start + end) / 2;
    int leftSum  = query(tree, 2 * node,     start, mid,     l, r);
    int rightSum = query(tree, 2 * node + 1, mid + 1, end,   l, r);
    return leftSum + rightSum;
}

// Usage:
// int result = query(tree, 1, 0, n - 1, l, r);

Query Complexity: Why O(log n)?

Let's prove this more carefully. The claim is that a range query visits at most O(log n) nodes.

The Counting Argument

Consider any level of the tree. There are at most 2level nodes at that level. For a query [l, r]:

• At most 2 nodes at each level have partial overlap (one touching the left boundary l, one touching the right boundary r). These are the only nodes where we recurse into both children.
• All other nodes visited at that level are total-overlap (we stop) or no-overlap (we stop).

Since the tree has ⌈log2 n⌉ + 1 levels, we recurse into both children at most O(log n) times. Each such split adds one node to the "frontier." The total nodes visited is bounded by 4 · log n (more precisely, at most 4 · ⌈log2 n⌉ - 5 for n ≥ 3).

Complete Implementation

class SegmentTree {
    int n;
    vector<int> tree;

    void build(const vector<int>& arr, int node, int s, int e) {
        if (s == e) {
            tree[node] = arr[s];
            return;
        }
        int mid = (s + e) / 2;
        build(arr, 2 * node,     s, mid);
        build(arr, 2 * node + 1, mid + 1, e);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    int query(int node, int s, int e, int l, int r) {
        if (r < s || e < l) return 0;
        if (l <= s && e <= r) return tree[node];
        int mid = (s + e) / 2;
        return query(2 * node, s, mid, l, r)
             + query(2 * node + 1, mid + 1, e, l, r);
    }

public:
    SegmentTree(const vector<int>& arr)
        : n(arr.size()), tree(4 * n, 0) {
        build(arr, 1, 0, n - 1);
    }

    int query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }
};

Common Mistakes

• Off-by-one in mid: The split must be mid = (start + end) / 2, with left covering [start, mid] and right covering [mid+1, end]. Getting this wrong causes missing or double-counted elements.
• Wrong identity value: For sum, return 0 on no-overlap. For min, return INT_MAX. For max, return INT_MIN. Using the wrong identity silently produces wrong answers.
• Insufficient array size: Always allocate 4 * n. Allocating 2 * n causes out-of-bounds for non-power-of-2 sizes.
• Mixing 0-indexed and 1-indexed: The tree is 1-indexed (root at 1), but the array can be 0-indexed. Be consistent.

Summary

• Build: Recursive divide-and-conquer. Leaves store array values, internals merge children. O(n) time.
• Query: Three cases at each node — total overlap (return value), no overlap (return identity), partial (recurse both). O(log n) time.
• At most 2 partial-overlap nodes per level, so the total work is bounded by the tree height.
• The tree array uses 1-based indexing with 4n space: children of node i are 2i and 2i+1.
• For a faster, non-recursive alternative, see the Iterative Segment Trees post.

In the next post, we'll see how point updates work and set the stage for lazy propagation.