Задачник Базовый курс EN

Как устроен

префиксные суммы

Статьи

SRT Алгоритм Сортировка подсчётом и поразрядная Без сравнений: посчитать ключи или разложить их по цифрам — O(n + k) и O(d·n) вместо n log n. O(n + k) и O(d·(n + b)) 2 задачи DS Структура данных Дерево Фенвика Суммы на префиксе с изменениями за O(log n) в одном массиве: блоки длиной в младшую единицу номера. O(log n) на сумму префикса и на изменение 2 задачи STR Приём Полиномиальный хеш Хеш любого куска строки за O(1) из хешей начал: сравнение подстрок, окна, общие начала — с оценкой вероятности ошибки. O(n) подготовка, O(1) хеш куска 2 задачи DP Приём Динамика на отрезках Состояние — отрезок [i, j], переход — где его разрезать: дерево поиска, порядок умножения матриц, распил. O(n³) 2 задачи TEC Приём Префиксные суммы Сумма любого отрезка за O(1) после одного прохода; двумерный вариант считает сумму любого прямоугольника картинки. O(n) на построение, O(1) на запрос 2 задачи

Задачи

Сколько выпало дождя Место в каталоге Одинаковые куски Распил бревна Ровно ноль градусов Сверка реплик Сушь Без сдачи Декодер Когда начинать заново Счастливые в диапазоне Тренд по любому окну Штрихи на рейке Блуждание по папкам Кэш любого размера

Часто рядом

классика 4 олимпиады 4 массив 3 битовые трюки 2 собеседования 2 в проде 2 запросы на отрезке 2 матрица 2 сортировка 1 устойчивость 1 бор 1 контроль версий 1