# Platinum

The topics below are not exhaustive for this division.

Contest problems may contain topics not covered in the guide, or topics listed under different divisions!

Some lower-frequency topics are included in "Advanced."

### Modules Progress

### Problems Progress

## Range Queries

More Applications of Segment Tree

Somewhat Frequent

Walking on a Segment Tree, Non-Commutative Combiner Functions

Range Queries with Sweep Line

Not Frequent

Solving 2D grid problems using 1D range queries.

Range Update Range Query

Rare

Lazy updates on segment trees and two binary indexed trees in conjunction.

Sparse Segment Trees

Rare

Querying big ranges.

2D Range Queries

Rare

Extending Range Queries to 2D (and beyond).

Divide & Conquer - SRQ

Rare

Using Divide & Conquer to answer offline or online range queries on a static array.

Square Root Decomposition

Rare

Splitting up data into smaller chunks to speed up processing.

## Trees

Binary Jumping

Somewhat Frequent

Efficiently finding ancestors of a node.

Updated: Last month

Small-To-Large Merging

Rare

A way to merge two sets efficiently.

Heavy-Light Decomposition

Rare

Path and subtree updates and queries.

Updated: Last month

Centroid Decomposition

Rare

Decomposing a tree to facilitate path computations.

## Geometry

Geometry Primitives

Rare

Basic setup for geometry problems.

Updated: Last week

Sweep Line

Rare

Introduction to line sweep.

Convex Hull

Not Frequent

Smallest convex polygon containing a set of points on a grid.

Convex Hull Trick

Not Frequent

A way to find the maximum or minimum value of several convex functions at given points.

## Misc. Topics

Inclusion-Exclusion Principle

Rare

The inclusion-exclusion principle is a counting technique that generalizes the formula for computing the size of union of n finite sets.

Matrix Exponentiation

Rare

Repeatedly multiplying a square matrix by itself.

(Optional) Bitsets

Rare

Examples of how bitsets give some unintended solutions on recent USACO problems.

Divide & Conquer - DP

Rare

Using Divide & Conquer as a DP Optimization.