rmq算法

发布时间：2020-12-16 07:48:35 所属栏目：百科来源：网络整理

导读：今天PHP站长网 52php.cn把收集自互联网的代码分享给大家，仅供参考。 1. 概述 void RMQ(int num) //预处理-O(nlogn) { for(int j = 1; j 20; ++j) for(int i = 1; i = num; ++i) if(i + (1 j) - 1 = num) { maxsum[i][j]

以下代码由PHP站长网 52php.cn收集自互联网

现在PHP站长网小编把它分享给大家，仅供参考

1. 概述

    void RMQ(int num) //预处理->O(nlogn)  
    {  
        for(int j = 1; j < 20; ++j)  
            for(int i = 1; i <= num; ++i)  
                if(i + (1 << j) - 1 <= num)  
                {  
                    maxsum[i][j] = max(maxsum[i][j - 1],maxsum[i + (1 << (j - 1))][j - 1]);  
                    minsum[i][j] = min(minsum[i][j - 1],minsum[i + (1 << (j - 1))][j - 1]);  
                }  
    }

这里我们需要注意的是循环的顺序，我们发现外层是j，内层所i，这是为什么呢？可以是i在外，j在内吗？

以上内容由PHP站长网【52php.cn】收集整理供大家参考研究

如果以上内容对您有帮助，欢迎收藏、点赞、推荐、分享。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!