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{8}{7})$.It is quicker than ST Table both in theory and practice.↵
↵
And then I create second idea.As we all know there is an 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 an algo of $O(n\alpha(n))$.↵
↵
Ah somebody tell me that I need to talk about Four Russian,so I'll tell it.↵
↵
The algo Four Russian can solve RMQ problem in a time complexity of $O(n\log \log n)-O(1)$.↵
↵
It is work like that:we divide the array to $O(\frac{n}{\log n})$ parts and each parts got $O(\log n)$ items.↵
↵
We set up an ST Table to uphold the maximum value between block and block,and between each block.↵
↵
Obviously we can get answer using these.↵
↵
The time complexity is $O(\frac{n}{\log n}\log n\log \log n)=O(n\log \log n)$.↵
↵
FeS2_qwq independently invented this algorithm.↵
↵
Lumos_QwQ and zhaoyuebo tested the theoretical correctness of this algorithm.↵
↵
zyb_txdy coding for it.↵
↵
[jiangbowen_](/profile/jiangbowen_ "Tourist jiangbowen_") help it a lot.↵
↵
You can find the algo Sqrt Tree on [here](https://codeforces.net/blog/entry/57046).↵
↵
Fun fact:when I finish it,CF crashed I use mirror to post it.
↵
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{8}{7})$.It is quicker than ST Table both in theory and practice.↵
↵
And then I create second idea.As we all know there is an 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 an algo of $O(n\alpha(n))$.↵
↵
Ah somebody tell me that I need to talk about Four Russian,so I'll tell it.↵
↵
The algo Four Russian can solve RMQ problem in a time complexity of $O(n\log \log n)-O(1)$.↵
↵
It is work like that:we divide the array to $O(\frac{n}{\log n})$ parts and each parts got $O(\log n)$ items.↵
↵
We set up an ST Table to uphold the maximum value between block and block,and between each block.↵
↵
Obviously we can get answer using these.↵
↵
The time complexity is $O(\frac{n}{\log n}\log n\log \log n)=O(n\log \log n)$.↵
↵
FeS2_qwq independently invented this algorithm.↵
↵
Lumos_QwQ and zhaoyuebo tested the theoretical correctness of this algorithm.↵
↵
zyb_txdy coding for it.↵
↵
[jiangbowen_](/profile/jiangbowen_ "Tourist jiangbowen_") help it a lot.↵
↵
You can find the algo Sqrt Tree on [here](https://codeforces.net/blog/entry/57046).↵
↵
Fun fact:when I finish it,CF crashed I use mirror to post it.
