feature image

2021年4月23日 | ブログ記事

BITについてちょっとだけ数学っぽく考えてみた【新歓ブログリレー46日目】

この記事は 新歓ブログリレー2021 46日目の記事です。

はじめに

最近競プロを少し頑張ってるあみだです。
2月頃から書いてましたが適当にだらだらした結果もう4月です。

BIT(Binary Indexed Tree)という、競技プログラミングなどで用いられるデータ構造について話しています。
セグメント木(Segment Tree)の発展版っぽいやつです。

競プロ初心者なので用語の使い方がおかしいかもしれませんが、ご愛嬌。

導入

ABC190のF問題でBITに出会った。
色々調べたけどお気持ちだけの絵とか魔法の x&-x とかで意味がわからなかったので、もう少し厳密に理解したいと思ったのがこれを書いたきっかけ。

元ネタ論文(Fenwick, 1994, p.328)の発想が一番自然で理解しやすかったのでこれに習った。(とはいえ元ネタを見る前に自分で考えたものなので自己流解釈あるかも)

数式を使った証明メインでやっていきます。
間違いがあったら教えていただけると幸いです。
投稿者Twitter

そもそもBITとは

Binary Indexed Tree の略。
このデータ構造を木っぽく表したとき、高さが同じところのIndexをBinaryで見ると、いい感じになってることが由来だと思う。(これはBinary Indexed Tree のはなしの40Pあたりを見てほしい)

扱うBIT

恐らく一般的なBIT。
ある数列があったとする。
要求は以下

  1. 一点更新をO(log)でできる
  2. 指定された範囲の合計をO(log)で求められる

1-indexedで考える。

具体的なデータ構造

大きさN+1の配列(名前をBITとする)
1-indexedなので事実上の大きさはN。

内訳

(プログラム的にはf(n)=n&-n で、なんでそうなるのかはn&-nの謎にて)

要は、indexがn以下のf(n)個の要素の合計。
(ちょっと記述怪しいけど流石に読み取ってください)

これだとわかりにくいので例を挙げると、
BIT[8] =
BIT[9] =
BIT[10] =
BIT[11] =
BIT[12] =

一点更新について

を加算する事を考える。

加算対象

ただし、

Pythonで書くとこんな感じ

update.pydef update(n, x):
    while n <= N:
        BIT[n] += x
        n += n&-n

上記の条件がa_nを更新することの必要条件であることを示すのは簡単だが、十分条件であることを示すのは厳しい。

必要条件であること

証明

帰納的に示す。

というようにnがカバーする範囲のようなものを定めると、以下が満たされていればいい。

まず、

部分を切り離して表せるので、

は整数だから、(mは奇数なので)以下のような不等式が成り立つ。

よって、

また、の定義より、

以上から、

つまり、の範囲をカバーする。

は推移律を持つので、帰納的に

必要条件の証明終わり

十分条件であること

証明を書いている途中に力尽きました。
お気持ちとしては、を一個ずつ上げていってをカバーするものを探すと、結局しかないよね、という話です。

書きかけの証明は一応残しておきます。

証明

まず、

であることを示す。
要は、をカバーするが存在する時、他にをカバーするようなが存在し無いということを言いたい。
のラインにをカバーするものが存在するかしないか、するならなのかだけ示せばよくなる。

を示せば良い。

としてよく、

なので、だから、

よって、

すると、今後示すべきは以下になる。とする。

に対し、
となるが存在するならば、となるが存在する。

ちょっと扱いづらいので、変形する。

だから、以上のことは次のように言い換えられる。
に対し、となるが存在するならば、

ここで証明は力尽きました。一応お気持ち説明をしておくと、
より大きいの倍数の中でHがnを含む可能性がある(含むとは限らない)のは証明の最初で言った唯一性から最小のものであることがわかる。
そして、それはなんだよ、ということが言える。

そうすると連鎖的にがnを含むことはわかるけれども、を並べてみると飛び飛びに並んでしまう。

あとは、その間に抜けがないか、つまりだが、ではないが存在しないか、ということをチェックすればOK。

大小条件とかをちゃんと書くと、

を証明すればOKということ。

以上です、m(__)m

計算量

更新箇所は平均で
元ネタ論文(Fenwick, 1994, P332)にはって書いてある気がするけど(誤読してたらすみません)、計算&実験してみたらこうなってしまった...
まあ1しか違わないからヨシ!

Nが2の累乗のときの証明をする。(元ネタ論文もそのときに限ってた)
まあどうせO(log)なのでそれ以外でも誤差。

証明

BIT[n]は個の要素をカバーしてるので、
平均更新量Uは以下のように表せる。

そして、
となるようなN以下のnの個数をとすると、
のときであり、のときである。

この事の証明(思ったよりも長くなってしまった)

まず、
のとき

のときと表せる。

のときなんでこうなるかというのは、書き出して考えて見るとわかるかもしれない。
前半部はの倍数の個数、後半部は指数がmより大きいものの個数。

あとは帰納的に示せるが、ほとんど明らかなので細かいところは省略。

これがわかれば容易。

Q_mの証明終わり

なんでなんてものを導入したかというと、Uの計算をするため。
は1ごとに上がって行き、当然1つずつ計算していく。
しかし、加算する値はで決まっているので、で分類して足したほうがいいだろうというわけ。

それを踏まえると、

計算量の証明終わり

指定範囲の合計算出について

基本的には1からnまでの和なのだが、それを組み合わせることで任意の範囲に対応できる。
よって、1〜nまでの合計の算出を考えれば十分。

これは一点更新より簡単。

返す値

返す値をとする。


である。

Pythonで書くとこんな感じ

get.pydef get(n):
    sum = 0
    while n > 0:
        sum += BIT[n]
        n -= n&-n
    return sum

hを複数回適用することでいつかはになる(0は自然数ですよ?)
だからそれで終了

これが正しいことを示すのは簡単。
再帰的にできる。

証明

あとはいつかに到達する(つまりは単調減少であること)を示せば良い。(といっても超簡単)

以上。

計算量

元ネタ論文(Fenwick, 1994, P331)によると、参照する個数は”平均で” って書いてあった(誤読してなければ)
オーダー感覚としてはそうなんだが、証明は不明悲しい気持ちを表明。

ちなみに、実験してみて帰納的に導き出せた平均は

だった。

まあ、
だからオーダーはO(log)程度だろうというある程度の予想はつくし、OK

n&-nの謎

n&-n = (nを割り切る最大の2)

??????

そもそも-nとは

&はビット演算子なので-nの2進法表現について考える。

マイナスを定義する時の気持ちとしてはマイナス値でも加算を滞りなくやりたい。
まず、nはint型で、これは全部でk桁の2進数で表現されているとする。

ここで、コンピュータ上でのnはnを表しているとは限らないことに注意したい。
というのも、(基本的に)使える桁数には限りがあるからである。

足し算や引き算をする時、k桁を超える、あるいはk桁では引かれる方の数の桁数が足りないということは十分に考えられる。

その時、超えた分を切り捨てたり足りない桁を仮につけたりする。
これはつまり、

これを踏まえると、

となるように

と決めたほうが都合が良い。

ちなみにこれを「2の補数」というらしい。

ビット的には...

ビット反転(~)して+1する。
※~を数式に埋め込むのが出来なかったので、(ニアリーイコール)を代わりに用いています...

ビット反転すると、1だったところは0になり、0だったところは1になる。
よって、

なので、

となっている。

実用上は

k桁をフルに使って数字を表現すると、となって都合が悪いので、
k-1桁で数字本体を表現して、k桁目が0ならプラス、1ならマイナスというように解釈する。

例:) k=8とする。
1: 00000001, 15: 00001111, 100: 01100100
-1:11111111, -15:11110001, -100:10011100

n&-nの動き

であったとする。
このとき、である。

なので、
(※当然だが、k-a-1桁のところはnの同一箇所をビット反転したもの)

(※k-a-1桁のところはnの同一箇所をビット反転したもの)

以上から、

おわりに

応用範囲も広くなく、セグ木で十分実現できるらしいのであまり理解する必要はなかったのかもしれない。

そんなことよりもMarkdownのTeX環境でチルダをうまく表現する方法を誰か教えて下さい。

参考文献

Binary Indexed Tree のはなし
Peter M. Fenwick, "A New Data Structure for Cumulative Frequency Tables" (1994)

明日は @lum1narie さんです。
お楽しみに

Amidadegomen_02 icon
この記事を書いた人
Amidadegomen_02

つまみ食いやってます

この記事をシェア

このエントリーをはてなブックマークに追加
共有

関連する記事

2021年3月19日
traPグラフィック班の活動紹介
NABE icon NABE
2021年4月2日
DXライブラリで重力パズルゲームを作る
Macky1_2 icon Macky1_2
2021年4月18日
ベズー係数とN項の拡張ユークリッドの互除法
0214sh7 icon 0214sh7
2018年12月12日
多重スリーブの世界と,各種進捗報告。
Silviase icon Silviase
2021年4月26日
CPCTF2021 作問者writeup by hukuda222
hukuda222 icon hukuda222
2021年4月25日
CPCTF2021 作問者writeup by xxpoxx
xxpoxx icon xxpoxx
記事一覧 タグ一覧 Google アナリティクスについて