A new idea to solve RMQ problem
Разница между en5 и en6, 2 символ(ов) изменены
My English is poor as a Chinese...↵

A few days ago I post an idea at a Chinese Online Judge named Luogu.This is my first idea created by myself to solve RMQ problem.↵
Unfortunately it's Chinese.The basic idea is divide the array into $n^\frac{4}{7}$ part,each part has a length of $n^\frac{3}{7}$.We name it as a "big block".Then we divide each block into $n^\frac{2}{7}$ part,each part has a length of $n^\frac{1}{7}$.Thus it can has a time complexity of $O(n^\frac{7}{8})$.It is quicker than ST Table both in theory and practice.↵

And then I create second idea.AWAK there is a algo called Four Russian.It can solve RMQ problem at a time complexity $O(n\log\log n)$.We found when we finish initialization,we are actually solve an RMQ problem but a smaller scale.Then we use Four Russian to this smaller RMQ problem,and then our time complexity become $O(n\log\log\log n)$.And we do it again while $n\neq 1$,it can do it in a time complexity of $O(n\log^*n)$.This can be called Sqrt Tree Set Four Russia(I like to call it as Log Tree)↵

This is a very outstanding algorithm but it's not enough.To improve it,we can set up many data structure and the .We set $T(m,n)$ to be the complexity of the $m$-layer data structure.We build a Sqrt Tree with $B=T(m-1,n)$ and let it be the $m$-layer data structure.Between block and block we use the $m-1$-layer data structure to solve the problem and in a block we use next layer of this data structure,then,as Base Four Russian Multiple Sqrt Tree(BFRMST) I called,finish.It is a algo of $O(n\alp
gha(n))$↵

FeS2_qwq independently invented this algorithm.↵

hegm made suggestions for improvement.↵

Lumos_QwQ and zhaoyuebo tested the theoretical correctness of this algorithm.↵

ZM____ML and wjh2022 coding for it.↵

wang_freedom and zh1221_qwq provide some stronger datas.↵

You can find the algo Sqrt Tree on [here](https://mirror.codeforces.com/blog/entry/57046).

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en34 Английский Butterfly_qwq 2024-12-07 09:27:33 24 Tiny change: 'iangbowen_ "\ntourist jiangbowen_") help it ' -> 'iangbowen_) help it '
en33 Английский Butterfly_qwq 2024-12-07 09:26:48 11
en32 Английский Butterfly_qwq 2024-12-07 09:25:47 20 Tiny change: 'owen_ "\nLegendary Grandmaster jiangbowe' -> 'owen_ "\nLGM jiangbowe'
en31 Английский Butterfly_qwq 2024-12-07 09:25:22 24 Tiny change: 'ngbowen_ "tourist jiangbowe' -> 'ngbowen_ "\nLegendary Grandmaster jiangbowe'
en30 Английский Butterfly_qwq 2024-12-07 09:24:47 2 Tiny change: 'ngbowen_ "Tourist jia' -> 'ngbowen_ "tourist jia'
en29 Английский Butterfly_qwq 2024-12-07 09:24:04 76
en28 Английский Butterfly_qwq 2024-09-11 14:51:19 5 Change Title
en27 Английский Butterfly_qwq 2024-09-11 14:18:37 99
en26 Английский Butterfly_qwq 2024-09-11 05:52:08 451
en25 Английский Butterfly_qwq 2024-09-10 16:46:55 129
en24 Английский Butterfly_qwq 2024-09-10 16:15:30 9 Tiny change: 'to be $O(\alpha(n)\log n)$\n' -> 'to be $O(\log n)$\n'
en23 Английский zhaoyuebo 2024-09-10 13:45:49 7 Tiny change: '](https://mirror.codeforces' -> '](https://codeforces'
en22 Английский Butterfly_qwq 2024-09-10 13:43:04 37 Tiny change: 'e it here.\n\nFeS2_q' -> 'e it here.It is seem to be $O(\alpha(n)\log n)$\n\nFeS2_q'
en21 Английский Butterfly_qwq 2024-09-10 13:42:32 2 Tiny change: ':sometime U will thin' -> ':sometime I will thin'
en20 Английский Butterfly_qwq 2024-09-10 13:42:11 73
en19 Английский zhaoyuebo 2024-09-04 06:16:26 16 Tiny change: 'ond idea.AWAK there is ' -> 'ond idea.As we all know there is '
en18 Английский zhaoyuebo 2024-09-04 06:14:07 1 Tiny change: 'alpha(n))$\n\nFeS2_q' -> 'alpha(n))$.\n\nFeS2_q'
en17 Английский Butterfly_qwq 2024-08-19 09:11:31 1 Tiny change: 'there is a algo call' -> 'there is an algo call'
en16 Английский Butterfly_qwq 2024-08-16 11:35:24 1 Tiny change: 'sh.It is a algo of $' -> 'sh.It is an algo of $'
en15 Английский Butterfly_qwq 2024-08-16 11:21:37 0 (published)
en14 Английский Butterfly_qwq 2024-08-16 11:20:17 126 (saved to drafts)
en13 Английский Butterfly_qwq 2024-08-16 10:00:36 0 (published)
en12 Английский Butterfly_qwq 2024-08-16 10:00:24 4 Tiny change: 'O(n^\frac{7}{8})$.It is ' -> 'O(n^\frac{8}{7})$.It is ' (saved to drafts)
en11 Английский Butterfly_qwq 2024-08-16 09:53:58 0 (published)
en10 Английский Butterfly_qwq 2024-08-16 09:53:45 0 (saved to drafts)
en9 Английский Butterfly_qwq 2024-08-16 09:47:00 0 (published)
en8 Английский Butterfly_qwq 2024-08-16 09:46:45 65 (saved to drafts)
en7 Английский Butterfly_qwq 2024-08-16 09:44:11 0 (published)
en6 Английский Butterfly_qwq 2024-08-16 09:43:48 2 Tiny change: 'f $O(n\alpga(n))$\n\n' -> 'f $O(n\alpha(n))$\n\n'
en5 Английский Butterfly_qwq 2024-08-16 09:43:26 31 Tiny change: 'ed,finish.\n\nFeS2_q' -> 'ed,finish.It is a algo of $O(n\alpga(n))$\n\nFeS2_q'
en4 Английский Butterfly_qwq 2024-08-16 09:42:29 919
en3 Английский Butterfly_qwq 2024-08-16 09:10:51 454
en2 Английский Butterfly_qwq 2024-08-15 10:42:25 22 Tiny change: 'ctice.\n\n' -> 'ctice.\n\nTo be continued...\n\n'
en1 Английский Butterfly_qwq 2024-08-15 10:40:47 530 Initial revision (saved to drafts)