Preparation to IOI Part 4 - Comprehensive Course

Module 1: Trie

Trie

Module 2: Sparse Table

Sparse table

Module 3: Segment Tree

Segment tree
Maximum subarray sum on a given segment

Module 4: Segment Tree Lazy propagation

Segment Tree with Lazy Propagation

Module 5: More on trees

Euler order of visiting vertices
DP on a tree (Tree DP)

Module 6: Binary jumping

Binary Lifting (Jumps)
Lowest common ancestor

Module 7: Cyclic Games

Games on Cyclic Graphs

Module 8: Divide & Conquer

Divide and conquer

Module 9: SQRT Techniques

SQRT Decomposition
SQRT heuristics
Mo’s Algorithm

Home Courses Resources Problems National Olympiad Contests Leaderboard

...

Home/Courses/Preparation to IOI Part 4

Preparation to IOI Part 4

Study the powerful techniques and data structures used in harder problems. This course covers trie, sparse table, segment tree, lazy propagation, tree techniques, binary jumping, divide and conquer, cyclic games, and sqrt methods.

9 modules

·

14 lessons

Part 1

Module 1: Trie

Trie

Trie
Trie

Part 2

Module 2: Sparse Table

Sparse Table

Sparse table
Sparse table

Part 3

Module 3: Segment Tree

Segment Tree

Segment tree
Segment tree
Maximum subarray sum on a given segment
Maximum subarray sum on a given segment

Part 4

Module 4: Segment Tree Lazy propagation

Segment Tree Lazy propagation

Segment Tree with Lazy Propagation
Segment Tree with Lazy Propagation

Part 5

Module 5: More on trees

tin/tout and their properties, all Euler orders, etc

Euler order of visiting vertices
Euler order of visiting vertices
DP on a tree (Tree DP)
DP on a tree is a class of problems where the values at a vertex are computed based on the values of its children in the DFS tree.

Part 6

Module 6: Binary jumping

Binary jumping

Binary Lifting (Jumps)
Binary Lifting (Jumps)
Lowest common ancestor
Lowest common ancestor

Part 7

Module 7: Cyclic Games

Game theory on cyclic graphs

Games on Cyclic Graphs
Games on Cyclic Graphs

Part 8

Module 8: Divide & Conquer

Divide & Conquer

Divide and conquer
Divide and conquer

Part 9

Module 9: SQRT Techniques

SQRT Techniques

SQRT Decomposition
SQRT Decomposition
SQRT heuristics
SQRT heuristics
Mo’s Algorithm
Mo’s Algorithm