CodeBlanks Logo Icon CodeBlanks
Login Register

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.

Practice 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])).

Starter code

solution.py
def build_segment_tree(arr):
    # Build segment tree

Sample solution

solution.py
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]))

Expected output

[0, 16, 4, 12, 1, 3, 5, 7]

Questions and answers

Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.

1 Segment tree: match the terms

Term Meaning
tree[1] 16 (sum)
tree[2] 4 (left)
tree[3] 12 (right)
tree[4] 1 (leaf)

2 What is the segment tree root for [1, 3, 5, 7]?

  • 4
  • 7
  • 16 Correct answer
  • 12

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

3 Inner node computation

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

Explanation: 2 is right.

All lessons in Advanced

1 DP - Memoization

  1. What is memoization?
  2. Fibonacci memoization
  3. Dict-based cache
  4. Summary - Memoization

2 DP - Tabulation

  1. What is tabulation?
  2. Building the table
  3. Fibonacci tabulation
  4. Summary - Tabulation

3 LCS

  1. LCS definition
  2. DP table
  3. Backtracking the table
  4. Summary - LCS

4 Knapsack

  1. Knapsack problem
  2. 0/1 knapsack DP
  3. Decision table
  4. Summary - Knapsack

5 DP project

  1. Project: Overview
  2. Cost table
  3. DP solution
  4. Print the result

6 Matrix chain

  1. Multiplication order
  2. DP table
  3. Split point
  4. Summary - Matrix chain

7 Floyd-Warshall

  1. All pairs
  2. Triple loop
  3. Table update
  4. Summary - Floyd-Warshall

8 Dijkstra

  1. Single source
  2. Priority queue
  3. Relaxation
  4. Summary - Dijkstra

9 Bellman-Ford

  1. Negative weights
  2. Edge relaxation loop
  3. Negative cycle
  4. Summary - Bellman-Ford

10 Kruskal

  1. Minimum spanning tree
  2. Edge sorting
  3. Cycle check
  4. Summary - Kruskal

11 Prim

  1. Prim idea
  2. Priority queue
  3. Visited set
  4. Summary - Prim

12 Topological sort

  1. Dependency order
  2. DFS-based sort
  3. Kahn algorithm
  4. Summary - Topological sort

13 Union-find, trie, segment tree

  1. Union-find
  2. Trie
  3. Segment tree
  4. Summary - Advanced structures

14 Advanced final

  1. Challenge 1
  2. Challenge 2
  3. Challenge 3
  4. Challenge 4