RMQ問題のSTアルゴリズム

ソース:http://www.cnblogs.com/ljsspace/archive/2011/08/04/2127317.html
彼のブログには多くのオンラインアルゴリズムがあります.本編は計算O(1)時間で無秩序配列のある区間の最小値を調べます.
ST(Sparse Table)アルゴリズムの基本的な考え方は、始点A[i]から長さ2のj乗(j=0,1...logn)の区間の最小値を計算してから、照会時にどの区間A[i.j]を2つの前処理が可能な重複区間に分割し、この2つの重複区間の最小値をとることである.
前処理段階では、始点A[i]から、どの長さが2^jの区間でも、2つの長さ2^(j-1)の区間に分けられます.ここで、最初の区間の範囲は、i...i+2^(j-1)-1です.第二の区間の範囲はi+2^(j-1)...i+2^j-1です.M[i,j]でA[i]から2^jの区間(つまりA[i]….A[i+2^j-1])の最小値に対応する下付きを表します.すると、A[M[i,j]=min{i……(j+2)-1]、A[i+2^(j-1)...i+2 j-1.  DP思想を利用して、M［i,j−1］の値を先に計算し、M［i,j］の値を計算する.
照会段階では、任意の区間A[i.j]の長さd=j-i＋1、k=flook(logd)を使用すれば、この区間は2つの長さ2^kのサブ区間によって完全にカバーされ、この2つの長さは2^kの区間に重複することができる.この二つの区間は前処理で最小値を求められているので、両者の最小値を取ってA［i.j］の最小値を得ることができる.
STアルゴリズム前処理段階の複雑さはO(nlogn)であり、クエリ段階の複雑さはO(1)である.
実装:
?/** *  * Using ST(Sparse Table) algorithm to solve RMQ problem * time complexity: <O(nlogn),O(1)> *  *   * Copyright (c) 2011 ljs (http://blog.csdn.net/ljsspace/) * Licensed under GPL (http://www.opensource.org/licenses/gpl-license.php)  *  * @author ljs * 2011-08-02 * */public classRMQ_ST {          //ST: O(nlogn) for preprocessing    publicint[][] preprocess(int[] A){        intn = A.length;        //floor value        intmaxJ=(int)(Math.log(n)/Math.log(2));                  int[][] M = newint[n][maxJ+1];                  //initial condition for dynamic programming: the RMQ for interval length=1        for(int i = 0; i < n; i++)              M[i][0] = i;                  //dynamic programming: compute values from smaller(j=1) to bigger intervals        for(int j = 1; j<=maxJ; j++){            for(int i = 0; i + (1<< j) - 1 < n; i++){                intnexti = i + (1 << (j - 1));                if(A[M[i][j - 1]] <= A[M[nexti][j - 1]])                    M[i][j] = M[i][j - 1];                else                    M[i][j] = M[nexti][j - 1];            }        }        returnM;    }          //ST: O(1) for querying    publicintquery(int[] A,int[][] M,inti,int j){        if(j<i){            //swap i and j            inttmp=i;i=j;j=tmp;        }        intk = (int)(Math.log(j-i+1)/Math.log(2));        //the first interval        intmina = M[i][k];        intminb = M[j-(1<<k)+1][k];        if(A[mina]<=A[minb])            returnmina;        else            returnminb;    }      publicstaticvoid main(String[] args) {                int[] A=newint[]{0,1,2,3,7,1,9,2,8,6};        RMQ_ST st = newRMQ_ST();        int[][] M = st.preprocess(A);                            System.out.format("%n***********************%n");               inti=3,j=7;                intmin = st.query(A,M, i,j);        System.out.format("RMQ for A[%d..%d]: A[%d]=%d", i,j,min,A[min]);                  System.out.format("%n***********************%n");        j=3;i=7;            min = st.query(A,M, i,j);        System.out.format("RMQ for A[%d..%d]: A[%d]=%d", i,j,min,A[min]);                  System.out.format("%n***********************%n");        for(intx=0;x<A.length;x++){            for(inty=0;y<x;y++){                System.out.format("    ");            }            for(inty=x;y<A.length;y++){                intp = st.query(A,M,x,y);                              System.out.format(" %d/%d",A[p],p);            }            System.out.println();        }       }  }