Segment tree

Segment tree answers range queries.

Segment tree

A segment tree enables range queries (sum, min, max) on an array. It is built in O(n) space; queries answer in O(log n) time.

For array [1, 3, 5, 7], the sum segment tree has root 16, left 4, right 12 as a 7-node tree.

Tree construction

The segment tree is represented as an array: tree[1] is root, tree[2i] and tree[2i+1] are left/right children. Leaves are the array itself.

Construction places leaves at the end and fills inner nodes as the sum of their children.

Exercise build_segment_tree function

Write build_segment_tree(arr). Build the tree array: place leaves at the end, fill inner nodes with child sums. Print it with print(build_segment_tree([1, 3, 5, 7])).

Show example solution

def build_segment_tree(arr):
    # Build segment tree
    n = len(arr)
    tree = [0] * (2 * n)
    for i in range(n):
        tree[n + i] = arr[i]
    for i in range(n - 1, 0, -1):
        tree[i] = tree[2 * i] + tree[2 * i + 1]
    return tree
print(build_segment_tree([1, 3, 5, 7]))

Test yourself

Segment tree: match the terms

tree[1]

16 (sum)
tree[2]

4 (left)
tree[3]

12 (right)
tree[4]

1 (leaf)
What is the segment tree root for [1, 3, 5, 7]?
- 4
- 7
- 16
- 12
Show answer

16 — Root is the sum of all elements: 1+3+5+7=16.

Inner node computation

tree[i] = tree[2*i] + tree[____*i+1]

Show answer

tree[i] = tree[2*i] + tree[2*i+1]

Next lesson: Summary - Advanced structures

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies