ST表（查询区间最值问题）

ST表与线段树相比，这是静态的，无法改动，但是他的查询速度比线段树要快，这是牺牲空间换时间的算法。

O(nlogn)预处理，O(1)查询。空间O(nlogn)。

int d[][];

int mn[];

void rmq_init()

{

    for(int i=;i<=n;i++)

        d[i][]=a[i];

    for(int j=;(<<j)<=n;j++)

      for(int i=;i+(<<j)-<=n;i++)

        d[i][j]=min(d[i][j-],d[i+(<<(j-))][j-]);

    for(int len=;len<=n;++len){

        int k=;

        while((<<(k+))<=len)

            k++;

        mn[len]=k;

    }

}

int rmq(int L,int R)

{

    int k=mn[R-L+];

    return min(d[L][k],d[R-(<<k)+][k]);

}

巴特西

ST表（查询区间最值问题）

最新文章

热门文章