Хотите RMQ за O(log log) с линейным предподсчётом?
Делим массив на sqrt (N) кусочков. На кусочках строим полный предподсчёт за O(K²). А на каждом кусочке — рекурсивно аналогичную структуру.
[update] Предподсчёт всё же не линейный, а O(N·log log N), столько же памяти.
Делим массив на 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.
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 просмотров.
0 репостов,
3677 просмотров.
Эту запись оставил(а) на своей стене Олег Давыдов
