精华内容
下载资源
问答
  • ST算法

    2021-02-28 15:18:24
    题目描述 输入一串数字,给你 M个询问,每次询问就给你两个数字X,y ,要求你说出 X 到 Y这段区间内的最大数。 输入格式 第一行两个整数M,M 表示数字的...ST算法ST算法是用来解决区间最值得一种算法原理是倍增 ...

    题目描述
    输入一串数字,给你 M个询问,每次询问就给你两个数字X,y ,要求你说出 X 到 Y这段区间内的最大数。

    输入格式
    第一行两个整数M,M 表示数字的个数和要询问的次数;
    接下来一行为N 个数;
    接下来 M 行,每行都有两个整数 X,Y。

    输出格式
    输出共 M行,每行输出一个数。

    样例
    输入
    10 2
    3 2 4 5 6 8 1 2 9 7
    1 4
    3 8
    输出
    5
    8
    这道题运用到了ST算法。
    什么是ST算法?
    ST算法:ST算法是用来解决区间最值得一种算法原理是倍增
    它能在O(nlogn)的时间预处理,然后O(1)回答。dp[i][j]表示从i位起的2^j 中最大的数即[i,i+2^j-1]中的最大值

    #include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<algorithm>
    using namespace std;
    
    const int maxn=1e5+100;
    int n,m,x,y;
    int dp[maxn][30],a[maxn];
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
           scanf("%d",&a[i]);
           dp[i][0]=a[i];
        }
        for(int j=1;j<=log2(n);j++)
            for(int i=1;i+(1<<j)-1<=n;i++)
            dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
        for(int i=1;i<=m;i++)
        {
           scanf("%d%d",&x,&y);
           int k=log2(y-x+1);
           printf("%d\n",max(dp[x][k],dp[y-(1<<k)+1][k]));
        }
        return 0;
    }
    
    
    展开全文
  • ST 算法

    千次阅读 2019-05-15 22:03:17
    给定一个长度为N的数列 A ,ST算法能在时间的预处理后,以O(1)的时间复杂度在线回答" 数列 A 中下标在 l ~ r 之间最大的值是多少" ,这样的区间最值问题 。 设表示数列A 中下标在子区间里的数的最大值 ,也就是从 i ...

    在RMQ问题(区间最值问题) 中 , ST 算法就是倍增的产物 。给定一个长度为N的数列 A ,ST算法能在 O(NlogN) 时间的预处理后,以O(1)的时间复杂度在线回答" 数列 A 中下标在 l ~ r 之间最大的值是多少" ,这样的区间最值问题 。

    设 F [i,j] 表示数列A 中下标在子区间 [i ,i+2^{j}-1]里的数的最大值 ,也就是从 i 开始的 2^{j} 个数的最大值。递推边界显然是F[i,0] = A[i]  , 即数列 A 在子区间 [ i,j ] 里的最大值 。

    在递推时,我们把子区间的长度成倍的增长 ,有公式 F[i,j] = max(F[i,j-1],F[i+2^{j},j-1]) ,即长度为 2^{j} 的子区间的最大值是左右两半长度为 2^{j-1} 的子区间的最大值中的较大的一个。

    // 区间最值
    void ST_prework() { // st算法预处理
    	for(int i = 1 ;i<=n ; i++ ) {
    		f[i][0] = a[i] ; // 处理边界 [i,i] 的最大值就是 a[i]
    	}
    	int t = log(n)/log(2) + 1 ; // 这里是枚举右端点
    	for(int j =1 ; j<t ; j++){
    		for(int i = 1 ;i<=n-(1<<j)+1 ;i++) {
    		//	f[i][j] = max(f[i][j-1] ,f[i+(1<<(j-1))][j-1]) ;
    			f[i][j] = min(f[i][j-1] ,f[i+(1<<(j-1))][j-1]) ;
    		}
    	}
    	
    }

     

    当询问任意区间 [  L, R ] 的最值时, 我们先计算出一个 k  ,满足 2^{k} < r-l+1 <=2^{k+1} ,也就是使2 的k 次幂小于区间长度的前提下的最大 k 。那么, " 从 l 开始的 2^{k} 个数" 和"以 r 结尾的 2^{k}个数"这两段一定覆盖了整个区间 [ l,r ] ,这两段的最大值分别是 F[l,k] 和 F[r-2^k +1 , k] ,二者中较大的那个就是整个区间的最值。

     

    int ST_query(int l ,int r){ // 查询 区间 [l,r] 之间的最值
    	int k = log(r-l+1)/log(2);
    	return max(f[l][k],f[r-(1<<k)+1][k]) ;
    }

     

    展开全文
  • st算法

    2020-12-24 08:48:20
    下面的对数器明明单步是对的,连在一起就不对 #include<iostream> #include<vector>...int ST(int l, int r, vector<vector<int> >&dp) { int k = (int)ceil(log(r-l+1)

    1.RMQ问题

    先说问题,RMQ(Range Minimum/Maximum Query,即区间最值查询),一个数组随机获取[l,r]范围内的最值,当然如果要获取其它特征的数据也是同理。

    2.ST算法

    2.1 算法内容

    数组a={2,3,6,9,5,0,1};

    数组长度n=a.size()=7;

    数组dp;

    **第一步:用O(nlogn)的时间和空间复杂度的代价创建dp数组。**不过这个dp是相当的难想,dp[i][j]表示从i开始i+2ki+2^k个数据的最值。这个数据的范围很容易扣不明白边界。比如dp[0][0]表示的是数组a下标从0开始0+20=10+2^0=1个数据的最值,这个“1”是a[0]到a[1]还是只有a[0]自己?a[0]到a[1]是左闭右开还是左闭右闭(a[0]到a[1]的左闭右开和只有a[0]自己不是一个意思,因为当a[0]是最右边界的时候a[1]是不存在的,哪怕结果是一样的,思考方式可不同)?这几个问题当然是写代码的人自己规定的,我说说看我认为最方便的方法,我这里认为dp[0][0]表示的是a[0]自己,就是说加1从自己为0开始加。同理,dp[3][2]表示从a[3]开始3+22=73+2^2=7个数据的最值,即区间[3,9][3,9]的最值,右侧是闭区间。

    **第二步:DP数组的行列数。**按照我上面的规定,basecase很好写,dp的第一列就是数组a的内容,那么行数就固定了。第二个坑来了,那么有几列呢?我特意选了个比较坑的7来判断数组列数。我的第一反应是:log2n\lceil log_2 n \rceil,这道题自然log27=3\lceil log_2 7 \rceil=3,但是这就大错特错了。因为第k列表示i+2ki+2^k,也就是说,这个3不应该是列数,而是最大列数的下标,有第0列的存在,所以列数应该是4,最大列数是3。

    **第三步:向dp数组填表。**basecase第一列填好后,$ dp[i][j]=max(dp[i][j-1], dp[i+2^{j-1}, j-1]) $,理解为将dp[i][j]从中间分为两部分,左侧的结果自然就是dp[i][j-1],右侧区间的左边界就是dp[i][j-1]的右边界,因为是将dp[i][j-1]对半分,所以右区间的指数自然和左区间一样是j-1。可见不管是左区间还是右区间,因为纵坐标都是j-1,所以结果都可以通过前一列计算出来,所以填表的时候要按照列填,即第1列填完再填第2列。下面dp[6][1]其实是不存在的,因为a[6]已经是数组的最后一个元素,怎么可能还有2j12^{j-1}存在呢。有的代码会把这个位置空出来,但是我觉得还是都填上比较好,所以在下面要判断是否越界。

    2 3 9 9
    3 6 9 9
    6 9 9 9
    9 9 9 9
    5 5 5 5
    0 1 1 1
    1 1 1 1

    **第四步:查找。**实际查找dp[l][l]的时候,l和r的距离很可能不恰好等于2的某个次方,此时就要比较一次。例如
    k,l+2k<=r(k),dp[l][r]=max(dp[l][k],dp[r2k+1][k]) {\exist}k,满足l+2^k<=r(其中k为所有可能值中的最大值),那么dp[l][r] = max(dp[l][k], dp[r-2^k+1][k])
    从右往左数的时候,那个+1很容易落下,我目前没啥好的办法,只能用dp[0][1]来试。

    其中这个k的值是log2(rl+1)log_2 {(r-l+1)},这个+1的我也是试出来的。

    2.2 代码

    #include<iostream>
    #include<vector>
    #include<math.h>
    #include<algorithm>
    #include<ctime>
    #include<assert.h>
    using namespace std;
     
    void STpre(vector<int>&a,vector<vector<int> >&b)///左闭右闭
    {
        int m = a.size();
        int n = (int)ceil(log(m)/log(2)+1);///<这里是用边界有坑
        vector<vector<int> >dp(m, vector<int>(n,0));
        for(int i=0; i<m; ++i)
            dp[i][0] = a[i];
     
        for(int j=1; j<n; ++j)
        {
            for(int i =0; i<m; ++i)
            {
                auto aa = i+(1<<(j-1))<m ? dp[i+(1<<(j-1))][j-1] : dp[i][j-1];
                dp[i][j] = max(dp[i][j-1], aa);
            }
        }
        swap(b,dp);
    //    vector<vector<int> > ().swap(dp);
        return;
    }
    int STget(vector<vector<int> >dp, int l, int r)///<这里l和r是双闭的
    {
        int k = (int)floor(log(r-l+1)/log(2));
        return max(dp[l][k], dp[r-(1<<k)+1][k]);
    }
    int ST(vector<int>&a, int l, int r)///<左闭右开
    {
        assert(!a.empty());///<这个没法处理
        assert(l<=r);
        if(l==r)
            return a[l];
        vector<vector<int> >dp;
        STpre(a, dp);
        return STget(dp, l, r);
    }
     
    int test(int left,int right,vector<int>&a)
    {
        if(left>right || a.empty())
        {
            printf("a\n");
            return -1;
        }
        return *max_element(a.begin()+left, a.begin()+right+1);
    }
    void printa(vector<int>&a)
    {
        for(size_t i=0;i<a.size();++i)
            cout<<a[i]<<",";
        cout<<endl;
    }
    int main(void)
    {
        srand((unsigned)time(NULL));
        for(int i=0;i<10000;++i)
        {
            int len = 10000;///<len是个数上限
            int n = rand()%(len-1-1+1)+1;///<1~len-1,n是实际个数
            vector<int>a;
            for(int j=0;j<n;++j)
                a.push_back(rand()%(1000-0+1)+0);
     
            int left = rand()%(n-1-0+1)-0;///<0~n-1
            int right;
            if(left != n)
                right = rand()%(n-1-left+1)+left;///<left~n-1
            else
                right = left;
            int y=test(left,right,a);
     
            int x=ST(a, left, right);
            if(x!=y)
            {
                cout<<"left="<<left<<",right="<<right<<endl;
                printa(a);
                cout<<"st="<<x<<",test="<<y<<",n="<<n<<endl;
            }
        }
        return 0;
    }
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,079
精华内容 1,631
关键字:

st算法