Sparse table — различия между версиями
| Строка 7: | Строка 7: | ||
'''''Идея решения'''''<br> | '''''Идея решения'''''<br> | ||
| − | + | Будем предподсчитывать минимумы на полуинтервалах вида [i, i + 2^k). Разумеется, i e [0, n) | |
Версия 19:05, 4 апреля 2020
Задача RMQ.
Формулировка проблемы.
Есть массив, к нему поступают запросы вида "найти минимум из элементов этого массива с индексами от L до R (не включая R)".
Идея решения
Будем предподсчитывать минимумы на полуинтервалах вида [i, i + 2^k). Разумеется, i e [0, n)
