Где применяется
1. Задача
Два прошлых урока строили деревья отрезков. Они отвечают на запрос про отрезок и принимают изменения, и то и другое за O(log n). Теперь данные перестают меняться. Лог-файл закрывается в полночь, справочная таблица поставляется вместе с приложением, сетка головоломки задана заранее. Записей больше не будет. При этом на тысячи вопросов «какое наименьшее значение между индексами l и r» отвечать всё ещё надо.
Дерево отрезков здесь подойдёт, но O(log n) на запрос дороже, чем нужно. Если массив никогда не меняется, можно заранее посчитать столько, что каждый запрос минимума на отрезке будет стоить O(1). Эта структура называется разреженной таблицей.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи на массив, который не меняется, с большим числом вопросов про минимум, максимум или НОД на отрезке. После построения за O(n log n) два перекрывающихся блока отвечают на каждый отрезок за O(1). LeetCode не называет разреженную таблицу по имени, и большинство таких задач проходят и монотонный дек, и дерево отрезков.
Каждое окно это отрезок, так что один раз построй таблицу максимумов и отвечай на каждое окно за O(1). Дек из урока 56 делает это за O(n).
- 1438.Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (откроется в новой вкладке)Средняя
Расширяй окно двумя указателями и бери его максимум и минимум из двух таблиц, сдвигая левый край, пока разница больше limit.
Пусть a стоит раньше b. Если a равно b или b выше, ответ b. Иначе бинарным поиском найди первый индекс после b, где максимум на отрезке выше большего из двух.