FeS2_qwq's blog

By FeS2_qwq, history, 3 months ago, In English

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.

You can find the algo Sqrt Tree on here.

Fun fact:when I finish it,CF crashed I use mirror to post it.

  • Vote: I like it
  • +64
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by FeS2_qwq (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by FeS2_qwq (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by FeS2_qwq (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by FeS2_qwq (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by FeS2_qwq (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How can I delete these strange auto comment

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    when u're updating, uncheck the auto comment box

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

too classic

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Really?All right I think it's my own invention...

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by FeS2_qwq (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by FeS2_qwq (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by FeS2_qwq (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by zhaoyuebo (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by zhaoyuebo (previous revision, new revision, compare).

»
2 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

We found when we finish initialization,we are actually solve an RMQ problem but a smaller scale.

I cannot understand what this sentence is about. AFAIK The Method of Four Russians only support delta-1 RMQ.

Maybe you should contain an implementation in this post?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I'll upd when I have time.

    What you said is a improvement of Four Russian.

    Thanks for advice,upvote u.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

could you pls tell me where you posted this algorithm on Luogu?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You construct the data structure in $$$O(n^{\frac 8 7})$$$ but how would you answer a query better than $$$O(n^{\frac 2 7})$$$ this way?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Ah,let me think.

    That is not important(just kidding).

    All right I think I need to spend some time thinking it seriously.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Aha my code is O(1) to answer a query. You can initialize the answer in a block and between every block.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

You mentioned the sqrt tree blog. There is actually a second part: https://codeforces.me/blog/entry/59092

About update: sometime I will think of it carefully and write it here. It is seem to be $$$O(\alpha(n) \log n)$$$.

Can you please elaborate a little more about how to achieve such update complexity?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe update it in a sqrt-tree way?

    But I didn't think carefully of it is $$$O(\alpha(n)\log n)$$$ or $$$O(\frac{n\alpha(n)}{\log n})$$$.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The second part of the blog mentions that sqrt-tree updates only in $$$O(\sqrt{n})$$$ (and provides a way to do this). So this is an interesting question.

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Ah I know.It is $$$O(\alpha(n)\log n)$$$.

        I'll update Four Russian in 3 days and update in a week.

        Maybe I'll resolve it to two or three blogs.


        Correct:It can be solve in $$$O(\log n)$$$.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh I get it wrong.It cannot update (-:

        Mainly because we cannot update an ST Table

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I finish Four Russian.

»
2 months ago, # |
  Vote: I like it +10 Vote: I do not like it

seems the same as the algorithm described in this paper https://codeforces.me/blog/entry/131221?#comment-1167384