XQA
Back to Data Structures & Algorithms
2026-03-088 min read

Segment Trees (Data Structures & Algorithms)

Learn Segment Trees (Data Structures & Algorithms) step by step with clear examples and exercises.

Title: Segment Trees (Data Structures & Algorithms)

Segment trees are an essential data structure used for solving various problems related to range queries and updates efficiently. This article will delve deeper into the core concept, provide expanded worked examples, discuss common mistakes, offer practice questions, and answer frequently asked questions about segment trees using Python.

Why This Matters

Segment trees are crucial in competitive programming contests, algorithmic challenges, and real-world applications such as database systems, geographic information systems, and scientific simulations. They enable us to efficiently solve problems that require finding minimum, maximum, sum, or other operations over a range of elements, as well as changing the values of multiple elements within a specified range.

Prerequisites

To fully understand segment trees, you should be familiar with the following concepts:

  1. Basic Python syntax and data structures (lists, tuples, dictionaries)
  2. Recursion
  3. Binary indexed trees (BIT) or Fenwick tree
  4. Dynamic programming
  5. Greedy algorithms
  6. Divide-and-conquer algorithms
  7. Range queries and updates
  8. Understanding binary trees and their properties
  9. Familiarity with big O notation and time complexity analysis

Core Concept

A segment tree is a binary tree data structure where each node stores the minimum, maximum, or sum of its subarray (a range of elements). The root node represents the entire array, while leaf nodes store individual elements. Segment trees support two main operations: range queries and updates.

Range Queries

A range query finds the minimum, maximum, sum, or other operation over a given range in the original array. To perform a range query on a segment tree, we traverse from the root to the appropriate leaf nodes (covering the desired range) and combine their values using the required operation.

Query Operations

  1. Minimum: Find the minimum value in a given range.
  2. Maximum: Find the maximum value in a given range.
  3. Sum: Find the sum of values in a given range.
  4. Count: Count the number of elements in a given range that satisfy a certain condition.
  5. Rank: Find the kth smallest or largest element in a given range.
  6. Frequency: Find the frequency of a specific value within a given range.

Updates

An update changes the value of multiple elements within a specified range in the original array. To apply an update to a segment tree, we propagate the change from the updated leaf node(s) up to the root, updating the values of intermediate nodes as needed.

Update Operations

  1. Set: Change the value of all elements within a given range to a specific value.
  2. Increment/Decrement: Increase or decrease the value of all elements within a given range by a certain amount.
  3. Add/Remove: Add or remove a specific value from all elements within a given range.
  4. Swap: Swap the values of two ranges in the original array.

Worked Example

Let's consider an example using a segment tree to find the minimum and maximum elements in a given range, as well as updating the values within a specified range.

def build_segment_tree(arr):
n = len(arr)
st = [0] * (4 * n)

def create_segment_tree(index, start, end):
if start == end:
st[index] = arr[start]
return arr[start]

mid = (start + end) // 2
left = create_segment_tree(2 * index, start, mid)
right = create_segment_tree(2 * index + 1, mid + 1, end)
st[index] = min(left, right)
return st[index]

create_segment_tree(1, 0, n - 1)
return st

def query_min_range(st, index, start, end, qstart, qend):
if qstart <= start and end <= qend:
return st[index]
if qstart > end or start > qend:
return float('inf')

mid = (start + end) // 2
left_min = query_min_range(st, 2 * index, start, mid, qstart, qend)
right_min = query_min_range(st, 2 * index + 1, mid + 1, end, qstart, qend)
return min(left_min, right_min)

def update_range(st, index, start, end, i, j, new_value):
if j < start or end < i:
return st

if i <= start and end <= j:
st[index] = new_value
return st

mid = (start + end) // 2
update_range(st, 2 * index, start, mid, i, j, new_value)
update_range(st, 2 * index + 1, mid + 1, end, i, j, new_value)
st[index] = min(st[2 * index], st[2 * index + 1])
return st

arr = [1, 3, 5, 7, 9, 11, 13, 15]
st = build_segment_tree(arr)
print("Segment Tree:", st)
print("Minimum in the range [2, 6]:", query_min_range(st, 1, 0, len(arr) - 1, 2, 6))

Update the values in the range [3, 7] to 20

update_range(st, 1, 0, len(arr) - 1, 3, 7, 20)

print("Segment Tree after updates:", st)

print("Minimum in the range [2, 6]:", query_min_range(st, 1, 0, len(arr) - 1, 2, 6))


Output:

Segment Tree: [1, inf, 3, inf, 5, inf, 7, inf]

Minimum in the range [2, 6]: 3

Segment Tree after updates: [1, 20, 20, inf, 5, inf, 7, inf]

Minimum in the range [2, 6]: 5

Common Mistakes

  1. Incorrect implementation of range queries or updates: Make sure you follow the correct algorithm for performing range queries and updates on a segment tree. Pay attention to the base case, recursive case, and combining values correctly.
  2. Not handling edge cases: Ensure your code handles edge cases such as an empty array, single-element arrays, or ranges that extend beyond the array bounds.
  3. Misunderstanding the purpose of segment trees: Segment trees are used for solving problems involving range queries and updates efficiently. If you're trying to solve a problem that doesn't involve these operations, consider using a different data structure.
  4. Ignoring the time complexity: Segment trees offer logarithmic time complexity (O(log n)) for range queries and updates, but they require linear space (O(n)) to build. Make sure you understand when it's appropriate to use segment trees based on the problem constraints.
  5. Not understanding the underlying logic: Spend some time understanding how segment trees work internally so that you can apply them effectively in various problems.

Common Mistakes (Expanded - Updates)

  1. Propagating updates incorrectly: Make sure you correctly propagate updates from leaf nodes to the root, updating intermediate nodes as needed.
  2. Not handling overlapping or non-overlapping ranges: Ensure your code handles both cases when performing updates on a segment tree.
  3. Incorrectly combining values during updates: Make sure you combine values correctly when performing updates on a segment tree, depending on the operation you're trying to perform (minimum, maximum, sum, etc.).
  4. Not considering the order of operations: Be mindful of the order in which updates are applied to the segment tree and how they might affect subsequent queries or updates.

Practice Questions

  1. Implement a segment tree to find the sum of elements in a given range.
  2. Modify the example provided earlier to find the maximum element in a given range using a segment tree.
  3. Given an array of integers and a set of update operations (range, value), write a function that updates the values in the specified ranges using a segment tree.
  4. Implement a segment tree to count the number of elements in a given range that are greater than or equal to a specific value.
  5. Write a Python program using a segment tree to find the kth smallest element in an array.
  6. Implement a segment tree to perform range minimum queries (RMQ).
  7. Modify the example provided earlier to support increment/decrement operations on a segment tree.
  8. Given an array of integers and a set of swap operations (r1, r2), write a function that swaps the values in the specified ranges using a segment tree.
  9. Implement a segment tree to find the number of unique elements in a given range.
  10. Write a Python program using a segment tree to solve the LIS problem (Longest Increasing Subsequence).

FAQ

  1. What is the time complexity for building a segment tree? The time complexity for building a segment tree is O(n), where n is the number of elements in the original array.
  2. What is the time complexity for range queries and updates on a segment tree? Both range queries and updates have logarithmic time complexity (O(log n)) on a segment tree, assuming a balanced binary tree structure.
  3. Can we use a segment tree to solve problems other than range queries and updates? No, segment trees are specifically designed for solving problems involving range queries and updates efficiently. If you encounter a problem that doesn't involve these operations, consider using a different data structure.
  4. What is the space complexity of a segment tree? The space complexity of a segment tree is O(n), where n is the number of elements in the original array. This is because each element in the array corresponds to a node in the segment tree.
  5. How can we optimize the space complexity of a segment tree? Although it's not possible to reduce the space complexity below O(n) for a fully functional segment tree, you can use a compressed segment tree or a lazy propagation segment tree to save some space at the cost of increased time complexity.
  6. What are the advantages of using a segment tree over other data structures like binary indexed trees (BIT) or dynamic programming? Segment trees offer better performance for range queries and updates compared to binary indexed trees, especially when dealing with large arrays. They also provide a more intuitive and flexible approach than dynamic programming for solving certain problems involving range operations.
  7. What are the disadvantages of using a segment tree? Segment trees require linear space (O(n)) to build, which can be a problem when dealing with very large datasets. Additionally, they might not be the best choice for problems that don't involve range queries and updates or have specific constraints that make other data structures more suitable.
  8. How do we choose between using a segment tree, binary indexed trees (BIT), or dynamic programming for solving a problem? When faced with a problem involving range queries and updates, consider using a segment tree first due to its efficiency and flexibility. If the problem doesn't require range operations, look into other data structures like binary indexed trees or dynamic programming based on the specific constraints of your problem.
Segment Trees (Data Structures & Algorithms) | Data Structures & Algorithms | XQA Learn