1. Амортизированный анализ
1.1 t_{1..n}, phi_{0..n}, a_{1..n}, avg
1.2 Утверждения о связи sum t_i и sum a_i
1.2.1 sum t_i = sum a_i + deltaphi_loss
1.2.2 phi_0 = 0, phi_i >= 0 => sum t_i <= sum a_i
1.2.3 avg = O(max a_i) + deltaphi_loss / n

2. Примеры амортизации
2.1 вектор
2.2 пример: x^2 + y^2 = N; +плохие потенциалы; +соображения как подбирать потенциал
2.3 [optional] структура данных push(x), pop(cnt)
2.4 монетки

3. бинпоиск
3.1 простой: ищем числа в массиве
3.2 по предикату
3.3 ищем lower_bound через 3.2
3.3.1 фиктивные границы, upper_bound, STL, ищем последний элемент <= x
3.4 вещественный бинпоиск на примере кубического многочлена, точность

4. [два указателя]
4.1 снова ищем числа в массиве, уже умеем sort+bs
4.2 пусть запросы уже посорчены, тогда O(n+q)
4.3 offline решение если не посорчены
4.4 ещё два указателя: std::merge, std::set_intersection, упоминаем другие похожие функции

5. Хештаблица
5.1 мотивирующие примеры: add(x), remove(x), count(x), если x малые можно массив
5.2 хештаблица через separate chaining
5.3 хештаблица с open addressing
5.4 примеры хеш функций: hash(x) = x % M, hash(x) = [(a * x + b) mod p] mod M.