Хотите RMQ за O(log log) с линейным предподсчётом?...

Хотите RMQ за O(log log) с линейным предподсчётом?

Делим массив на sqrt (N) кусочков. На кусочках строим полный предподсчёт за O(K²). А на каждом кусочке — рекурсивно аналогичную структуру.

[update] Предподсчёт всё же не линейный, а O(N·log log N), столько же памяти.
Want RMQ for O (log log) with linear pre-calculation?

Divide the array into sqrt (N) pieces. On the pieces we build the full pre-calculation for O (K²). And on each piece - a recursively similar structure.

[update] The pre-calculation is still not linear, but O (N · log log N), the same amount of memory.
У записи 19 лайков,
0 репостов,
3677 просмотров.
Эту запись оставил(а) на своей стене Олег Давыдов

Понравилось следующим людям