区間の最値を解く-RMQ-STアルゴリズムの紹介

解析
STアルゴリズムはRMQ(Range Minimum/Maximum Query)の古典的なアルゴリズムであり、生まれながらにして区間の最値を求めるために使われているが、最値を維持することはできない.つまり、過程で区間のある要素の値を変えることはできない.O(nlogn)の前処理とO(1)のクエリは,大量のクエリが必要なシーンに非常に適している.次に,STアルゴリズムの処理手順を詳細に説明する.
たとえば、10の長さの配列があります.

1 3 2 4 9 5 6 7 8 0  

STアルゴリズムがdp配列を前処理しているため,素朴な線形ルックアップ,複雑度O(n)を用いる場合,STアルゴリズムはO(1)の時間複雑度しか必要としない[1,7]間の最大値をクエリする.
iからの2^j個の数の最値をdp[i][j]で表し、dp[i][j]の「管轄」index=iからの2^j個の数を表すと、どの区間も2つのdp要素に管轄されることは明らかである.例えば上記の[1,7]は、dp[1][2]とdp[4][2]に管轄され、max(dp[1][2]、dp[4][2])は[1,7]の最値である.
どのようにしてdp[1][2]とdp[4][2]の2つの要素を得ますか?簡単に、dp[1][n](2^n<=区間個数)のnをできるだけ大きくして最初の要素を得ることで、2番目の要素を推定することができ、2つの要素の管轄範囲の大きさは同じである.
これにより、dp配列を1つ前に処理するだけでよいが、この前処理は動的に計画されたプロセスであり、移行方程式は次のようになっている.

dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);

一方,dp配列の前処理とRMQの解法はちょうど逆過程である.
実戦
POJにはSTアルゴリズムのテンプレート問題Balanced Lineupがあり、2つの配列を前処理するだけで、1つは最大値を表し、もう1つは最小値を表す.
完全なコード:

#include
#include
#include
#include
using namespace std;
#define N 50005
int maxn[N][32], minn[N][32]; 
int a[N];

void ST(int n) {
  for (int i = 1; i <= n; i++)
    maxn[i][0] = minn[i][0] = a[i];

  int k = log(n * 1.0) / log(2.0);

  for (int j = 1; j <= k; j++)
    for (int i = 1; i <= n; i++) {
    if (i + (1 << j) - 1 > n) break;
      maxn[i][j] = max(maxn[i][j - 1], maxn[i + (1 << (j - 1))][j - 1]);
      minn[i][j] = min(minn[i][j - 1], minn[i + (1 << (j - 1))][j - 1]);
    }
}

int getAns(int x, int y) {
  int k = log(y - x + 1.0) / log(2.0);
  return max(maxn[x][k], maxn[y + 1 - (1 << k)][k]) - min(minn[x][k], minn[y + 1 - (1 << k)][k]);
}

int main() {
  int n, cas;
  scanf("%d%d", &n, &cas);
  for (int i = 1; i <= n; i++)
    scanf("%d", &a[i]);

  ST(n);

  while (cas--) {
    int x, y;
    scanf("%d%d", &x, &y);
    printf("%d
", getAns(x, y));
  }

  return 0;
}

Javascriptテンプレート:

var G = {
  dp: [], // dp[i][j]     index=i       2^j        

  init: function(a) {
    var n = a.length;

    for (var i = 0; i < n; i++)
      G.dp[i] = [], G.dp[i][0] = a[i]; 

    var k = ~~(Math.log(n) / Math.log(2));

    for (var j = 1; j <= k; j++)
      for (var i = 0; i < n; i++) {
        if (i + (1 << j) - 1 >= n) break;
        //         ，   Math.min()   
        G.dp[i][j] = Math.max(G.dp[i][j - 1], G.dp[i + (1 << (j - 1))][j - 1]); 
      }
  },

  getAns: function(x, y) {
    var k = ~~(Math.log(y - x + 1) / Math.log(2));
    //         ，   Math.min()   
    return Math.max(G.dp[x][k], G.dp[y + 1 - (1 << k)][k]);
  }
};


var a = [1, 3, 2, 4, 8, 7, 6, 5, 9, 0]  //     RMQ    

G.init(a);


// test cases
for (var i = 0; i < 10; i++)
  for (var j = i + 1; j < 10; j++) {
    var tmp = a.slice(i, j + 1)
      , normalAns = Math.max.apply(null, tmp)
      , stAns = G.getAns(i, j);

    if (normalAns !== stAns)
      console.log('Algorithm went wrong!');
  }