Skip to content

Divide and conquer [mp]

Micro pattern

Description

Split a problem into smaller pieces, solve them independently, and combine their results.

Problems

Trees

Choose a root and construct or count independent left and right subtrees.

Sorting

Split or partition ranges and sort their independent parts.

Interval optimization

Choose a final operation separating an interval into independent subproblems.