Skip to content
CCC Python Course

Doubling and binary lifting on sequences

Stage
6
Module
M6.12
Lessons
1

In this module

  • Build and query a binary-lifting table to jump O(log n) steps in a sequence.
  • Apply binary lifting to find ancestors in trees and reachable nodes in a graph.
  • Optimize queries by precomputing powers of two.

Before this module

M4.15Circular arraysM4.5Mathematical insight: parity, invariants, closed forms

Lessons

  1. 1Doubling and binary lifting on sequences

Practice

Try these on the judges. Each link opens the problem on WMOJ or DMOJ.

  1. 2022 S3
    Good Samples (opens on WMOJ in a new tab) WMOJ

    Follow a queue of linked instructions to find the first one that fires.

  2. 2019 S3
    Arithmetic Square (opens on DMOJ in a new tab) DMOJ

    Find the maximum value on the path between two nodes in a tree.

    Why DMOJ: An older tree-query problem that still makes good practice for this module.