BIT
蟻本p.160~
BITとは？
Binary Indexed Treeという。フェニック木(Fenwick Tree)とも言う。
BITでは1~Nまでの累積〇〇しか求めることができない。つまり、値に変更がない場合はただの累積〇〇の方が楽。
1~rから1~(l-1)を引けば、実質区間が計算できる。
セグメント木の親戚みたいなもの(たぶん)。実装しやすい。
最下段の長さを「要素数N以上の2べき」にしなくていいので楽。好きな長さにできる
簡単に多次元に拡張できる。
1-indexed ← 添字が1から始まる！！！重要！！！こっちのほうが実装しやすい！
目次(予定)
目次
説明の前に…
基本操作
まず形から
RSBと横幅の関係
値の所得
何故RSBを引いていくのか？
更新
何故RSBを足していくのか？
BITが使える問題
実装例
2次元BIT
1次元での考え方
2次元へ拡張してみる
BITと区間加算
先に結果から
どうしてそれで良いのか
BIT上で二分探索
メリットは何
実装どうすんねん
説明の前に…
数字を2進数で表した時に一番右側にある1のことをRightmost Set Bitを略してRSBと呼ぶことにします…！ LSB(Least Significant Bit)と呼ぶこともありますが、LSBは「一番右側のビット(ex. 1110のLSBは0)」という意味でもとれる、というかググるとほとんどがこっちの意味なので、この記事ではRSBに統一することにします…
基本操作
まず形から
https://gyazo.com/c69fabc27d25dcf6a668616a1b2582ad
これがBITの基本的な形です。セグメント木から隣り合うブロックを消しまくった、みたいな感じです。
それぞれのブロックの右端から下に線を落としていった所に数字が書かれているイメージです。
数字は1から始まっていることに注意して下さい（0は使わないので…）
RSBと横幅の関係
それぞれのブロックの中に書かれている数字をよーく見ると、一番右に書かれている1(つまりRSB)が、そのブロックの横幅と同じであることが分かります。例えば6番目のブロックは「0110」となっていて、右から二番目の2のbitが立っているので、横幅が2であることが分かります。
因みにn番目のRSB、つまりn番目のブロックの横の長さは(n&-n)で所得できます。(n&-n)でできる理由はRSBの方にちょっとだけ書いたと思います… 値の取得
https://gyazo.com/0ddbd66baa63deaad2135f7369ba50da
右下から左上に上がっていくイメージ。
左上に上がる…「今いる所 - 今いる所の長さ(RSB)」で移動できる。つまりi -= (i&-i)みたいな。
何故RSBを引いていくのか？
「それぞれの位置が2進数で表されている」というのが重要なポイントです
例えば7は2進数で0111なので、長さ4と2と1のブロックの組み合わせで表されていることが分かります(■■■■+■■+■)
「そのブロックたちを右から拾っていく」ということを考えると、なぜ現在いるブロックのRSBを引いていくのかが理解しやすいですhttps://gyazo.com/96656ca6171f5d9c65907606f59ed2e9
更新
https://gyazo.com/5d7c79fb999c0223bca40f61551e6eb5
下から真上に串刺しをした時に刺さる部分が更新される。
「今いる所+今いる所の長さ(RSB)」で移動できる。つまりi += (i&-i)みたいな。
何故RSBを足していくのか？
「ブロックの右側はそのブロックの横幅ぶん、必ず空いている」という性質を使います。
今、とあるブロックの右端位置にいるとします。そこから、そのブロックの横幅ぶんだけ右に移動すると、その部分は上記の性質から、空白の位置に来ます。そこから上に上がっていけばさっきのブロックよりも横幅が大きいブロックにぶつかります（最後はぶつからないけど）
っていう雑な説明。
2進数で考えると、数学的にも納得いきやすいかも…？
BITが使える問題
実装とか細かいことは転倒数の記事の方に書いています
実装例
code:sample.cpp
// 1-indexedなので注意。
struct BIT {
private:
vector<int> bit;
int N;
public:
BIT(int size) {
N = size;
bit.resize(N + 1);
}
// 一点更新です
void add(int a, int w) {
for (int x = a; x <= N; x += x & -x) bitx += w; }
// 1~Nまでの和を求める。
int sum(int a) {
int ret = 0;
for (int x = a; x > 0; x -= x & -x) ret += bitx; return ret;
}
};
2次元BIT
1次元での考え方
まず2次元に入る前に、1次元の方のBITについてもう一度振り返ってみることにします。
「何故RSBを引いていくのか？」の部分に書いたように、iを2進数で表記するとiは2べきの組み合わせで表せて、それを使って1からiまでの和を求めていました。
例えば11を2進数で表すと1011(8+2+1)なので、8と2と1を組み合わせる、みたいな感じです。
https://gyazo.com/e9b2680356540f235e6809199a0ec7e0
これを1次元っぽく表すとこのようになります。（イメージです）
2次元へ拡張してみる
結果から見せると
https://gyazo.com/be17ae08beac4bee6a0b018ec9782b48
このようにすれば良いです。1次元と同じ「長さを2べきで表して順番に足す」を縦向きにも持ってきた、という感じです。実装は簡単で、1重ループの所を2重ループにすると実装できます。この要領で何次元でも増やせます。
code:BIT2dim(こんな感じ).cpp
// 位置(y,x)にwを足す
void add(int y, int x, int w) {
for (int i = y, i <= height; i += i&-i) {
for (int j = x; j <= width; j += j&-j) {
}
}
}
// (1,1)~(y,x)までの和を求める。
int sum(int y, int x) {
int ret = 0;
for (int i = y, i <= height; i -= i&-i) {
for (int j = x; j <= width; j -= j&-j) {
}
}
return ret;
}
BITと区間加算
BITでも、区間加算を実装することができます。
掛け算のおかげでl~r間の時だけ効果を発揮するBITと、そいつを裏で調整してあげるBITの2つのBITを使うイメージ。
BIT上で二分探索
メリットは何
編集途中なんですが…無限に更新しなさそう。いつか書きます
実装どうすんねん