222
правки
Изменения
м
Умные люди могут сразу же заметить, что решением Решением этого является <tex>T(n) = O(n \log n)</tex>. А люди моего уровня могут почитать умные книжки или просто поверить в данный факт. Хотя могу неформально пояснить: второе слагаемое даёт <tex>O(n)</tex> суммарно, а всего слагаемых из-за неё получится <tex>O(\log n)</tex>. То есть получим <tex>O(n)</tex> из-за второго слагаемого и ещё <tex>O(\log n)</tex> слагаемых вида <tex>O(n)</tex>.
Нет описания правки
<tex>T(n) = O(n) + 2 \cdot T(n / 2)</tex>, otherwise.
Также стоит отметить, что можно и не искать медиану за линейное время, а просто посортить все точки в самом начале и дальше использовать это. В реализации попроще, асимптотика та же.
}}
By the way, в общем случае время на запрос <tex>O(n^{1 - 1/k} + ans)</tex>. Быстренько прикинув, я получил соотношение из соотношения <tex>Q(n) = k + 2^{k - 1} \cdot Q(n / 2^k)</tex>. Кажется, так и есть, но это не особо надо, просто пусть будет, полезно же.
== Ссылки ==
