Sparse Tableを知ったので、忘れないように。

codeforces.com
この問題の想定解法がSparse Tableを使ったもので、ちゃんと理解したいなと思ったので忘備録的な感じで書きます。
色々調べながら書いているので、間違っているところがあったら指摘して頂けるとありがたいです。

Sparse Tableとは

まず、Sparse Tableがどういうものなのかを簡単に説明。

・ある区間に対する最小値、最大値を求められる。

・区間内のインデックスから長さがごとの区間内の最小値または最大値を持つインデックスを保持するデーブルを持つ

・区間内のインデックスごとに最小値または最大値を持つインデックスを見つけるので、テーブルの生成で

・クエリの処理を行う前にテーブルが出来ているので、

テーブルの生成

まず、でテーブルを生成していく。

区間の長さとして、配列を用意する。

A[0]	A[1]	A[2]	A[3]	A[4]	A[5]	A[6]	A[7]	A[8]	A[9]	A[10]	A[11]
2	5	3	9	8	2	10	1	7	2	1	6

ここで、ごとの区間のというのは以下のようなもの。

• 開始インデックス
• 区間の長さ

として最小値のインデックスを求める時、
,の場合、

A[0]	A[1]	A[2]	A[3]	A[4]	A[5]	A[6]	A[7]	A[8]	A[9]	A[10]	A[11]
2	5	3	9	8	2	10	1	7	2	1	6

,の場合、

A[0]	A[1]	A[2]	A[3]	A[4]	A[5]	A[6]	A[7]	A[8]	A[9]	A[10]	A[11]
2	5	3	9	8	2	10	1	7	2	1	6

,の場合、

A[0]	A[1]	A[2]	A[3]	A[4]	A[5]	A[6]	A[7]	A[8]	A[9]	A[10]	A[11]
2	5	3	9	8	2	10	1	7	2	1	6

,の場合、

A[0]	A[1]	A[2]	A[3]	A[4]	A[5]	A[6]	A[7]	A[8]	A[9]	A[10]	A[11]
2	5	3	9	8	2	10	1	7	2	1	6

ここで、を求める場合、が分かっていれば調べる区間の半分を既に調べていることになるので、残りの調べていない部分だけを調べれば良い。

A[0]	A[1]	A[2]	A[3]	A[4]	A[5]	A[6]	A[7]	A[8]	A[9]	A[10]	A[11]
2	5	3	9	8	2	10	1	7	2	1	6

開始インデックスが,長さがの場合の最小値を指すインデックス。
これをDPで求め、デーブルを生成する。

import java.util.Arrays;

public class RMQ_SparseTable {
	int[] A, log_table;
	int[][] table;
	int N;

	public RMQ_SparseTable(int[] A) {
		N = A.length;
		this.A = Arrays.copyOf(A, N);


		//log_tableを前処理で作っておくことでクエリ処理時にO(1)でlogを計算できる
		log_table = new int[N + 1];
		for(int i = 2;i < N + 1;i++){
			log_table[i] = log_table[i >> 1] + 1;
		}


		table = new int[N][log_table[N] + 1];


		//table[i][2^0] = i番目の要素から長さ1の区間の最小値はA[i](A[i]自身か含まないので)
		for (int i = 0; i < N; i++) {
			table[i][0] = i;
		}
		for (int k = 1;(1 << k) <= N; k++) {
			for (int i = 0; i + (1 << k)<=  N; i++) {
				int first = table[i][k - 1];//前部分
				int second = table[i + (1 << (k - 1))][k - 1];//後部分

				//前部分の最小値と後部分の最小値を比較して、より小さいものを採用する
				if (A[first] < A[second]) {
					table[i][k] = first;
				} else {
					table[i][k] = second;
				}

			}
		}
	}
}

クエリの処理

の最小値のインデックス
とする。
クエリの処理は,の2つの区間の最小値を求めることで最小値のインデックスを求める。

つまり、

は、つまりクエリの引数で指定された区間の長さをにしたもの。
こうすることで、は区間の半分以上を覆うことができ、もまた区間の半分以上を覆うことができるので、
区間全体を覆うことができる。

例：の場合

,,

A[0]	A[1]	A[2]	A[3]	A[4]	A[5]	A[6]	A[7]	A[8]	A[9]	A[10]	A[11]
2	5	3	9	8	2	10	1	7	2	1	6

A[0]	A[1]	A[2]	A[3]	A[4]	A[5]	A[6]	A[7]	A[8]	A[9]	A[10]	A[11]
2	5	3	9	8	2	10	1	7	2	1	6

例：の場合

,,

A[0]	A[1]	A[2]	A[3]	A[4]	A[5]	A[6]	A[7]	A[8]	A[9]	A[10]	A[11]
2	5	3	9	8	2	10	1	7	2	1	6

A[0]	A[1]	A[2]	A[3]	A[4]	A[5]	A[6]	A[7]	A[8]	A[9]	A[10]	A[11]
2	5	3	9	8	2	10	1	7	2	1	6

SparseTableの実装(Java)

import java.util.Arrays;

public class RMQ_SparseTable {
	int[] A, log_table;
	int[][] table;
	int N;

	public RMQ_SparseTable(int[] A) {
		N = A.length;
		this.A = Arrays.copyOf(A, N);


		//log_tableを前処理で作っておくことでクエリ処理時にO(1)でlogを計算できる
		log_table = new int[N + 1];
		for(int i = 2;i < N + 1;i++){
			log_table[i] = log_table[i >> 1] + 1;
		}


		table = new int[N][log_table[N] + 1];


		//table[i][2^0] = i番目の要素から長さ1の区間の最小値はA[i](A[i]自身か含まないので)
		for (int i = 0; i < N; i++) {
			table[i][0] = i;
		}
		for (int k = 1;(1 << k) <= N; k++) {
			for (int i = 0; i + (1 << k)<=  N; i++) {
				int first = table[i][k - 1];//前部分
				int second = table[i + (1 << (k - 1))][k - 1];//後部分

				//前部分の最小値と後部分の最小値を比較して、より小さいものを採用する
				if (A[first] < A[second]) {
					table[i][k] = first;
				} else {
					table[i][k] = second;
				}

			}
		}
	}

	public int query(int s, int t) {
		//区間の長さ
		int d = t - s + 1;
		//logの計算
		int k = log_table[d];

		if (A[table[s][k]] < A[table[t - (1 << k) + 1][k]]) {
			return table[s][k];
		} else {
			return table[t - (1 << k) + 1][k];
		}
	}
}

参考:
Range Minimum Query and Lowest Common Ancestor – topcoder
RMQ: Sparse Table - Algorithms and Data Structures

まとめ

写経をしているはずなのに、なぜかバグが生まれるのがだいぶ辛かった。