Skip to content
CCC Python Course

Segment tree (iterative, custom merge)

Stage
7
Module
M7.1
Lessons
1

In this module

  • Explain how a segment tree builds a tree of summaries bottom-up from an array.
  • Implement an iterative segment tree with point updates and range queries.
  • Design a custom monoid for combining values in a specific way.
  • Optimize Python segment tree code for speed on PyPy.

Before this module

M6.10Fenwick tree (Binary Indexed Tree)M4.3Prefix sums (1D, 2D, prefix/suffix max)M7.4Exchange arguments, scheduling and greedy proofs

Lessons

  1. 1Segment tree structure and custom merges

Practice

Try this on the judge. The link opens the problem on WMOJ.

  1. 2025 S5
    To-Do List (opens on WMOJ in a new tab) WMOJ

    Find the total time after applying range queries on a task list with deadlines.