BITを使ってみた

データ構造 CodeChef C++

前に出たCodeChefのコンテストで解けなかった問題を解いてみました。

Magic Board
http://www.codechef.com/problems/MBOARD

N*NのフィールドとQ個のクエリが与えられる。
クエリは
RowSet i x: i行目をx(=0 or 1)にする。
ColSet i x: i列目をx(=0 or 1)にする。
RowQuery i: i行目の0の数を答える。
ColQuery i: i列目の0の数を答える。

N, Q <= 500000なのでシミュレーションは無理。
i行目の0の数を知るには、
・最後のRowSet i xのxが0か1か
・最後のRowSet i xのあとにColSet j (xの逆) が何個発生したか分かれば良い。

全く分かりませんでしたが、BITを使ってタイムスタンプを覚えておけば出来るらしいです。

MBOARD Editorial
http://discuss.codechef.com/questions/6379/mboard-editorial


BITってなんだ？？ということで調べてみました。
BITというのはBinary Indexed Treeの略で、Fenwick Treeともいうそうです。例えば長さnのIntの配列が与えられた時にi〜j番目の総和などをO(logn)時間で計算できます。

調べてみると、構造的にはセグメント木のようなイメージですが、実装がものすごく簡単。
なんと、C++でadd、queryが以下の短さで書けます。驚きの短さ！

//配列のindex番目にvalを足す操作
void add(int *ary, int index, int val){
	int t = index;
	if(t == 0) return;
	while(t <= q + 1){
		ary[t] += val;
		t += t&(-t);
	}
}
//配列の先頭からindex番目までの総和を取る操作
int query(int*ary, int index){
	int ret = 0;
	int t = index;
	while(0 < t){
		ret += ary[t];
		t -= t&(-t);
	}
	return ret;
}

詳しくは調べてみてください。t & (-t)でtの最後のビットが取れるのがポイント。あとBITでは0-indexではなくて1-indexの方が簡単な気がします。

参考 : http://spinda2.blog48.fc2.com/blog-entry-427.html


BITを使ってMagic Boardを解いたコードはこちら(http://www.codechef.com/viewsolution/1844022)。
フィールドが始め0になっていますが、これは仮想的に1個目のクエリとし、i回目のクエリをi + 1回目とすると分かりやすいと思います。