Segment trees for range queries in Data Structures Theory - Mini Project: Build & Apply

Segment trees for range queries

📖 Scenario: Imagine you have a list of daily temperatures for a week. You want to quickly find the highest temperature in any range of days without checking each day one by one.

🎯 Goal: Build a simple segment tree structure that helps find the maximum temperature in a given range efficiently.

📋 What You'll Learn

Create an initial list of temperatures for 7 days

Set up a segment tree array to store maximum values

Build the segment tree from the temperature list

Add a function to query the maximum temperature in a given range

💡 Why This Matters

🌍 Real World

Segment trees are used in applications like weather data analysis, gaming, and databases where fast range queries are needed.

💼 Career

Understanding segment trees helps in software engineering roles that require efficient data processing and algorithm optimization.

1

Create the temperature list

Create a list called temperatures with these exact values: [23, 25, 19, 30, 28, 22, 24] representing daily temperatures.

Data Structures Theory

# Create the temperatures list
# Your code here

Need a hint?

Use square brackets to create a list and separate numbers with commas.

2

Set up the segment tree array

Create a list called segment_tree with size 15 filled with zeros to store the segment tree nodes.

Data Structures Theory

temperatures = [23, 25, 19, 30, 28, 22, 24]
# Create the segment_tree list with 15 zeros
# Your code here

Need a hint?

Use multiplication to create a list of zeros of the required size.

3

Build the segment tree

Write a function called build_tree that takes index, start, and end as parameters and builds the segment tree by storing maximum values from temperatures into segment_tree. Use recursion and update segment_tree[index] with the maximum of its children.

Data Structures Theory

temperatures = [23, 25, 19, 30, 28, 22, 24]
segment_tree = [0] * 15
# Define the build_tree function to fill segment_tree with max values
# Your code here

Need a hint?

Use recursion to build left and right children, then store the maximum in the current node.

4

Add the range maximum query function

Write a function called range_max_query that takes index, start, end, left, and right as parameters and returns the maximum temperature in the range [left, right] using the segment tree. Handle cases where the current segment is outside, partially inside, or fully inside the query range.

Data Structures Theory

temperatures = [23, 25, 19, 30, 28, 22, 24]
segment_tree = [0] * 15

def build_tree(index, start, end):
    if start == end:
        segment_tree[index] = temperatures[start]
        return
    mid = (start + end) // 2
    build_tree(2 * index + 1, start, mid)
    build_tree(2 * index + 2, mid + 1, end)
    segment_tree[index] = max(segment_tree[2 * index + 1], segment_tree[2 * index + 2])

build_tree(0, 0, len(temperatures) - 1)

# Define the range_max_query function to find max in a range
# Your code here

Need a hint?

Check if the current segment is outside, fully inside, or partially inside the query range and return the maximum accordingly.