Skip to content
Tutorials Center
My learning

Topics

Lesson 114 of 225 ยท Tries and Range Queries

Segment Trees

Learn segment trees in Python: build, range sum and min queries, point update, an iterative array version and lazy propagation for range updates, with complexity.

Suppose you keep an array of daily sales and answer two kinds of questions all day: "what is the total from day 40 to day 900?" and "the sales on day 57 were corrected to 120". With a plain loop, each query costs O(n). With prefix sums, a query costs O(1), but a single update forces you to rebuild O(n) prefix values. If both queries and updates come thousands of times, one of them is always slow.

A segment tree balances the two: both range queries and point updates take O(log n). It also works for far more than sums: minimum, maximum, gcd, "how many zeros in this range", and anything else where you can combine the answers of two halves. With lazy propagation it even supports "add 5 to every element in this range" in O(log n).

The idea

Split the array in half, then split each half, and so on until every piece is a single element. Store the answer (here, the sum) for every piece in a binary tree:

TEXT
array index:  0  1  2  3  4  5  6  7
values:       5  8  6  3  2  7  2  6

                    [0..7] = 39
              /                    \
        [0..3] = 22              [4..7] = 17
        /        \               /        \
   [0..1]=13   [2..3]=9     [4..5]=9    [6..7]=8
    /    \      /    \       /    \      /    \
   5      8    6      3     2      7    2      6

Every inner node stores combine(left child, right child), here left + right. The root answers the whole range. A tree over n elements has about 2n nodes and height about log2(n).

Range query. To answer sum(2..6), visit the tree from the root and, at each node, decide:

  • the node's range is completely outside the query: return the identity (0 for sums);
  • completely inside: return the stored value without going deeper;
  • partially overlapping: ask both children and combine.
TEXT
query sum(2..6) = 6+3+2+7+2

[0..7] partial  -> [0..3] partial -> [0..1] outside (0)
                                  -> [2..3] inside  (9)
               -> [4..7] partial -> [4..5] inside   (9)
                                 -> [6..7] partial  -> [6..6] inside (2)
                                                    -> [7..7] outside (0)
answer: 9 + 9 + 2 = 20

At each level at most two nodes are "partial", so the query touches O(log n) nodes.

Point update. Change a leaf, then recompute each ancestor on the way up: one node per level, O(log n).

A recursive segment tree

This version stores the tree in a list of size 4n (a safe upper bound for any n). Node i has children 2i and 2i + 1; the root is node 1.

Python Segment tree: build, query and update

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Checking against brute force

A good habit with range-query structures is to compare them with the obvious loop on random operations. It catches off-by-one errors in the boundaries.

Python Random test against a plain loop

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Beyond sums: any associative operation

Replace + with another combine function and the identity (the value that changes nothing) and you get a different structure:

Question combine identity
Range sum a + b 0
Range minimum min(a, b) infinity
Range maximum max(a, b) negative infinity
Range gcd math.gcd(a, b) 0
Range product mod m a * b % m 1

The operation must be associative ((a โˆ˜ b) โˆ˜ c = a โˆ˜ (b โˆ˜ c)), because the tree groups elements in an arbitrary shape. It does not need to be commutative if you keep left and right in order.

The iterative (bottom-up) version

For n elements, store the leaves in tree[n .. 2n-1] and build inner nodes from n-1 down to 1, where node i combines nodes 2i and 2i + 1. There is no recursion, so it is shorter and faster in practice. The tree need not be perfect: the formulas still work.

A query for the half-open range [left, right) climbs from both ends:

TEXT
left += n; right += n
while left < right:
    if left is odd:   take tree[left];  left += 1
    if right is odd:  right -= 1;  take tree[right]
    left //= 2; right //= 2

An odd left is a right child, so its parent would include elements outside the range; we take it alone and step right. The mirror rule applies to right.

Python Iterative segment tree with any combine function

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Lazy propagation: range updates

What if an update touches a whole range, such as "add 7 to every element in positions 2..5"? Updating each leaf costs O(n). The trick is to be lazy: when an update fully covers a node's range, update that node's stored value immediately and leave a note (a lazy tag) saying "my children still owe this add". Only when a later operation needs to look inside the node do we push the note down to the children.

For range-add with range-sum, a node covering len elements gets sum += value * len. The pending add is stored in lazy[node].

  1. Update/query reaches a node whose range is fully inside: apply and tag it. Do not descend.
  2. Update/query must go below a node: first push its tag to both children (apply to each child's sum, add to each child's tag, clear the node's tag).
  3. After recursing, recompute the node from its children.
Python Lazy segment tree: range add, range sum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Always test lazy structures with a brute-force comparison: forgetting one _push in either add or query is the most common bug, and it shows up only for certain query shapes.

Counting the savings

Let's measure how many array elements a naive range-add touches versus how many tree nodes the lazy version visits.

Python Naive range add vs lazy tree visits

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Complexity

Operation Time Notes
Build O(n) Each of the ~2n nodes is computed once
Range query O(log n) At most about 4 log n nodes visited
Point update O(log n) One root-to-leaf path
Range update (lazy) O(log n) Tags avoid touching leaves
Space O(n) 2n for the iterative layout, up to 4n for the recursive one

Choosing between range-query tools

Need Tool
Static array, sums Prefix sums, O(1) per query
Static array, min/max Sparse table, O(1) per query
Point updates + prefix sums Fenwick tree: shorter code, same O(log n)
Updates + arbitrary combine (min, gcd, ...) Segment tree
Range updates + range queries Lazy segment tree

Common mistakes

  • Array size too small. A recursive tree on n elements can need up to 4n slots; 2n can overflow when n is not a power of two.
  • Wrong identity. Using 0 for a minimum tree gives wrong answers; the identity must not change any result (infinity for min).
  • Inclusive vs half-open ranges. Decide once and stay consistent. The recursive examples above are inclusive; the iterative one is [left, right).
  • Forgetting to push before descending in a lazy tree, or forgetting to recompute the parent afterward.
  • Non-associative combine, such as subtraction or average: the results depend on how the tree groups the elements and will be wrong.
  • Rebuilding the tree for each update instead of updating one path.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What are the costs of a range query and a point update in a segment tree over n elements?

    A query visits a bounded number of nodes per level, and an update walks one leaf-to-root path; the height is about log n.
  2. 2. During a range query, what do you return for a node whose range is entirely inside the query range?

    A fully covered node already stores the answer for its whole range, so recursion stops there.
  3. 3. Which combine function is NOT suitable for a segment tree?

    The tree groups elements arbitrarily, so the operation must be associative; subtraction is not.
  4. 4. What is the purpose of the lazy tag in a lazy segment tree?

    The tag postpones the work: it is pushed down only when an operation needs to look inside the node.
  5. 5. Why does a recursive segment tree over n elements often allocate 4n slots?

    With children at 2i and 2i+1 the largest node index can approach 4n, so 4n slots are always enough.

Summary

  • A segment tree stores the answer for every power-of-two-style segment of an array in a binary tree.
  • Build in O(n); range query and point update in O(log n); memory O(n).
  • Any associative operation with an identity works: sum, min, max, gcd, and more.
  • The iterative bottom-up layout is shorter and faster; its queries use half-open ranges.
  • Lazy propagation delays range updates with tags and pushes them down only when needed, giving O(log n) range add and range sum.
  • Choose prefix sums or a sparse table when the data never changes, and a Fenwick tree when you only need prefix-style sums.

Next: Fenwick Tree (Binary Indexed Tree)