Изменения

Перейти к: навигация, поиск

Алгоритм Мо

6 байт убрано, 13:50, 22 декабря 2021
Исправление "медианы" описанной как "число, которое встречается больше всех остальных" на "моду"
'''Алгоритм Мо''' (англ. ''Mo's algorithm'') — применяется для решения задач, в которых требуется отвечать на запросы <tex>arr[l \ldots r]</tex> на массиве
''без'' изменения элементов в оффлайн за время <tex>O(Q \cdot \log{Q} + (N + Q) \cdot \sqrt{N})</tex>, где <tex>Q</tex> {{---}} количество запросов,
а <tex>N</tex> {{---}} количество элементов в массиве. Характерными примерами задач на этот алгоритм являются: нахождение медианы моды на отрезке (число, которое встречается больше всех остальных),
вычисление количества инверсий на отрезке.
Анонимный участник

Навигация