コンテンツにスキップ

BIT のリンク集

BIT(Binary Indexed Tree、Fenwick Tree)について、参考になる記事や資料をまとめました。

BIT は、列に対して「1 点への加算」と「先頭からの和(prefix 和)の取得」をどちらも O(log⁡N)O(\log N) で行えるデータ構造です。区間 [l,r)[l, r) の和は、2 つの prefix 和の差で求まります。セグメント木よりできることは少ないものの、実装が短く高速です。BIT を 2 本使った区間加算や、BIT 上の二分探索(累積和が ww 以上になる最初の位置を O(log⁡N)O(\log N) で求める)もよく使われます。

  • Binary Indexed Tree のはなし(hos、JOI 春合宿 2014 の講義スライド)
    • BIT の動きを図で 1 ステップずつ追いながら、1 点加算・prefix 和、区間加算、2 次元 BIT、BIT 上の二分探索まで解説しています。日本語の BIT 解説の定番です。
    • p.75 の二分探索の擬似コードの「n 以下の最小の 2 ベキ」は「最大」の誤りです。
  • Binary Indexed Tree (BIT) 総まとめ!区間加算や二次元BITまで(アルゴリズムロジック)
    • 1 点加算・区間和から、BIT 2 本による区間加算、BIT 上の二分探索、転倒数、2 次元 BIT までを図と C++ のコードでまとめています。練習問題も付いています。
    • 転倒数の手順は、値が 1 以上であることを前提にしています。値に 0 があるときは、1 を足すか座標圧縮してから使ってください。
  • fenwick_tree のドキュメント
    • 公式の仕様です。0-indexed で、区間和は半開区間 [l,r)[l, r) で求めます。BIT 上の二分探索はありません。

BIT を扱う講座はまだありません。

  • Binary Indexed Tree(Fenwick Tree)(ikatakos)
    • Python の実装集です。区間加算(BIT 2 本)、累積和の二分探索、BIT に載せられる演算の条件、座標圧縮や辞書を使った BIT、2 次元 BIT まで扱っています。
    • 区間加算版の sum に : の抜けがあり、演算を渡せる版の lower_bound はそのままでは動きません。通常版の Bit.lower_bound は正しく動きます。
  • Binary Indexed Tree(Luzhiled’s Library)
    • BIT 上の二分探索 lower_bound・upper_bound を備えた実装です。1 点加算は apply、区間和は prod という名前です。
  • Fenwick Tree(data-structures)
    • BIT でできる操作を、可換モノイドの場合とアーベル群の場合に分けて整理しています。参考資料や実装へのリンクもまとまっています。
  • Fenwick tree(英語版 Wikipedia)
    • 同じ配列を、部分和用・更新用・二分探索用の 3 つの木として見ることで、BIT の構造を説明しています。
  • フェニック木(日本語版 Wikipedia)
    • 英語版の古い版をもとにした短い記事で、細かい誤りがあります。たとえば多次元の場合の計算量が O(4dlog⁡dn)O(4^d \log_d n) になっていますが、引用元では O(4dlog⁡dn)O(4^d \log^d n) です。
  • Fenwick Tree(cp-algorithms)
    • 0-indexed と 1-indexed の両方の実装、2 次元 BIT、BIT 2 本による区間加算・区間和まで扱っています。練習問題も多く載っています。