BIT のリンク集
BIT(Binary Indexed Tree、Fenwick Tree)について、参考になる記事や資料をまとめました。
BIT は、列に対して「1 点への加算」と「先頭からの和(prefix 和)の取得」をどちらも で行えるデータ構造です。区間 の和は、2 つの prefix 和の差で求まります。セグメント木よりできることは少ないものの、実装が短く高速です。BIT を 2 本使った区間加算や、BIT 上の二分探索(累積和が 以上になる最初の位置を で求める)もよく使われます。
まず読むもの
Section titled “まず読むもの”- 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 を足すか座標圧縮してから使ってください。
AtCoder Library(ACL)
Section titled “AtCoder Library(ACL)”- fenwick_tree のドキュメント
- 公式の仕様です。0-indexed で、区間和は半開区間 で求めます。BIT 上の二分探索はありません。
AtCoder Algorithm Lectures
Section titled “AtCoder Algorithm Lectures”BIT を扱う講座はまだありません。
実装を詳しく知りたいとき
Section titled “実装を詳しく知りたいとき”- 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という名前です。
- BIT 上の二分探索
- Fenwick Tree(data-structures)
- BIT でできる操作を、可換モノイドの場合とアーベル群の場合に分けて整理しています。参考資料や実装へのリンクもまとまっています。
百科事典・英語の資料
Section titled “百科事典・英語の資料”- Fenwick tree(英語版 Wikipedia)
- 同じ配列を、部分和用・更新用・二分探索用の 3 つの木として見ることで、BIT の構造を説明しています。
- フェニック木(日本語版 Wikipedia)
- 英語版の古い版をもとにした短い記事で、細かい誤りがあります。たとえば多次元の場合の計算量が になっていますが、引用元では です。
- Fenwick Tree(cp-algorithms)
- 0-indexed と 1-indexed の両方の実装、2 次元 BIT、BIT 2 本による区間加算・区間和まで扱っています。練習問題も多く載っています。
- AtCoder Library Practice Contest B - Fenwick Tree:1 点加算・区間和の基本形です。
- Library Checker - Point Add Range Sum:上と同じ問題で、ライブラリの verify 用です。
- chokudai_S001 J - 転倒数:転倒数の基本形です。
- ABC190 F - Shift and Inversions:転倒数の応用です。
- ABC185 F - Range Xor Query:和の代わりに xor を載せる問題です。
- ABC276 F - Double Chance:値を添字にして、個数と和の BIT を 2 本持ちます。
- ARC033 C - データ構造:BIT 上の二分探索で 番目に小さい値を求めます。
このブログの記事
Section titled “このブログの記事”- SamCoding Round 7 (Div. 2) I - Subarrays in Range L-R
- 座標圧縮した累積和の個数を、Python 版では BIT で数えています。
- セグメント木のリンク集