読者です 読者をやめる 読者になる 読者になる

tookunn’s diary

主に競技プログラミング関係

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

メモ

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

Sparse Tableとは

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

・ある区間に対する最小値、最大値を求められる。
区間内のインデックスi(0 \leq i < N)から長さが2^kごとの区間内の最小値または最大値を持つインデックスを保持するデーブルを持つ
区間内のインデックスiごとに最小値または最大値を持つインデックスを見つけるので、テーブルの生成でO(NlogN)
・クエリの処理を行う前にテーブルが出来ているので、O(1)

テーブルの生成

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

table[N][log(N)]

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

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

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

  • 開始インデックス i
  • 区間の長さ 2^k

として最小値のインデックスを求める時、
i = 2,k = 0の場合、table[i][k] = 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

i = 2,k = 1の場合、table[i][k] = 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

i = 2,k = 2の場合、table[i][k] = 5

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

i = 2,k = 3の場合、table[i][k] = 7

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

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

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
table[i][k] = \left\{ \begin{array}{ll}
 table[i][k - 1] & (A [ table [ i ] [ k - 1 ] ] \leq A [ table [i + 2^{k - 1} - 1] [k - 1] ]) \\
 table[i + 2^{k - 1} - 1][k - 1] & (otherwise)
\end{array} \right.

table[i][k] = 開始インデックスがi,長さが2^kの場合の最小値を指すインデックス。
これを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;
				}

			}
		}
	}
}

クエリの処理

query(s,t) = A[s,t]の最小値のインデックス
とする。
クエリの処理はA[s,s + 2^k - 1],A[t - 2^{k} + 1,t]の2つの区間の最小値を求めることで最小値のインデックスを求める。

つまり、query(s,t) = min(A[s,s + 2^k - 1],A[t - 2^{k} + 1,t])を持つインデックス

kt - s + 1、つまりクエリの引数で指定された区間の長さをlog(t - s + 1)にしたもの。
こうすることで、A[s,s + 2^{log(t - s + 1)} - 1]区間の半分以上を覆うことができ、A[t - 2^{log(t - s + 1)} + 1,t]もまた区間の半分以上を覆うことができるので、
区間全体を覆うことができる。

例:query(0,11) = 7の場合

s = 0,t = 11,k = 3

A[i,i + 2^k - 1] = A[0,0 + 2^3 - 1] = A[0,7]

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[t - 2^{k} + 1,t] = A[11 - 2^3 + 1,11] = A[4,11]

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

例:query(2,4) = 2の場合

s = 2,t = 4,k = 1

A[s,s + 2^k - 1] = A[2,2 + 2^1 - 1] = A[2,3]

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[t - 2^{k} + 1,t] = A[4 - 2^1 + 1,4] = A[3,4]

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

まとめ

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