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\alpgha(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).
↵
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
↵
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).
