sparse table

目的

長さ$N$の数列$A$に対して、区間最小値の計算$\min_{l \le i\lt r}A[i]$を定数時間$O(1)$で行うデータ構造。

計算量

前計算$O(N\log N)$
区間最小値クエリ$O(1)$

使い方

int[] A
数列$A$
public SparseTable(int[] A)
数列$A$に対して前計算を行う。
long query(int l,int r)
$\min_{l \le i\lt r}A[i]$をreturn。

ソースコード


class SparseTable {
    int[][] t;

    public SparseTable(int[] A) {
	int N = A.length;
	t = new int[(int) (Math.log(N) / Math.log(2) + 1)][];
	t[0] = new int[(int) N];
	for (int i = 0; i < N; ++i) {
	    t[0][i] = A[i];
	}
	for (int i = 1; i < t.length; ++i) {
	    int p = 0;
	    while ((p + 1) + (1 << i) <= N)
		++p;
	    t[i] = new int[p];
	    for (int j = 0; j < t[i].length; ++j) {
		t[i][j] = Math.min(t[i - 1][j], t[i - 1][j + (1 << (i - 1))]);
	    }
	}
    }

    int query(int l, int r) {
	int a = 0;
	while (1 << (a + 1) <= (r - l)) {
	    ++a;
	}
	return Math.min(t[a][l], t[a][r - (1 << a)]);

    }

}

Verified

yukicoder No.515 典型LCP