Segment Tree (Range Sum Query) - Algorithm Tutorial

Segment Tree

A Segment Tree is a tree data structure for performing range queries and point updates in $O(\log n)$ time. It's also known as a statistic tree.

You build a binary tree where each node stores aggregate information (like sum, min, or max) for a range of the array.

text

function build(arr, tree, node, start, end):
    if start == end:
        tree[node] = arr[start]
        return
    mid = (start + end) / 2
    build(arr, tree, 2*node, start, mid)
    build(arr, tree, 2*node+1, mid+1, end)
    tree[node] = tree[2*node] + tree[2*node+1]

function query(tree, node, start, end, L, R):
    if R < start or end < L:
        return 0
    if L <= start and end <= R:
        return tree[node]
    mid = (start + end) / 2
    return query(tree, 2*node, start, mid, L, R) +
           query(tree, 2*node+1, mid+1, end, L, R)

function update(tree, node, start, end, idx, val):
    if start == end:
        tree[node] = val
        return
    mid = (start + end) / 2
    if idx <= mid:
        update(tree, 2*node, start, mid, idx, val)
    else:
        update(tree, 2*node+1, mid+1, end, idx, val)
    tree[node] = tree[2*node] + tree[2*node+1]

Array representation: You use an array of size $4n$ to store the tree. Node $i$ 's children are at $2i$ and $2i+1$ .

Applications: You use Segment Trees for range sum/min/max queries, lazy propagation for range updates, 2D queries, and competitive programming.

Time complexity: $O(n)$ to build, $O(\log n)$ per query or update.

Space complexity: $O(n)$ for the tree array.

Segment Tree (Range Sum Query) Algorithm Tutorial

Learn

Segment Tree

Implement this Algorithm

Related Algorithms