アルゴリズム/FenwickTree(BinaryIndexedTree) - projecthikky @ ウィキ

Fenwick Tree (または Binary Indexed Tree / BIT)

(日本語の呼び名は無いみたい、強引に訳すると、フェンウィック木、２進索引付き木？）

部分的な値の更新を繰り返す必要のあるデータの累積和を高速取得できるデータ構造？

wikipediaによると1994年にピーター・フェンウィック氏が提案したデータ構造とのこと

競プロの問題

---

日本語

北海道大学の競プロサークルによるスライド解説
https://www.slideshare.net/hcpc_hokudai/binary-indexed-tree

hos氏によるスライド解説(PDF)
http://hos.ac/slides/20140319_bit.pdf

naoya氏による解説
http://d.hatena.ne.jp/naoya/20090606/1244284915

anctgcc氏による解説(中学生にも分かるように説明しているらしい)
http://anctgcc.hatenablog.com/entry/2014/12/03/194140

hadori氏による概要
http://algoogle.hadrori.jp/algorithm/binary-indexed-tree.html

naos氏による概要
http://na-o-s.hateblo.jp/entry/2014/07/13/031143

Spaghetti Sourceによる概要
http://www.prefield.com/algorithm/container/fenwick_tree.html

---

英語

Wikipedia
https://en.wikipedia.org/wiki/Fenwick_tree

TopCoderでの解説記事
https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/

CS Academyでの解説記事
https://csacademy.com/lesson/fenwick_trees

HackerEarthでの解説記事
https://www.hackerearth.com/practice/notes/binary-indexed-tree-or-fenwick-tree/
https://www.hackerearth.com/practice/notes/binary-indexed-tree-made-easy-2/

HackerRankでの解説記事
https://www.hackerrank.com/topics/binary-indexed-tree

GeeksForGeeksでの解説記事
http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/

GeeksForGeeksのBITに関する記事一覧
http://www.geeksforgeeks.org/tag/binary-indexed-tree/

gvikei氏によるポイント説明
http://codeforces.com/blog/entry/619

動画解説
https://www.youtube.com/watch?v=v_wj_mOAlig
https://www.youtube.com/watch?v=CWDQJGaN1gY

Wolframによるデモンストレーション
http://demonstrations.wolfram.com/BinaryIndexedTree/

---

ライブラリ

Haskell
https://hackage.haskell.org/package/FenwickTree
https://hackage.haskell.org/package/binary-indexed-tree-0.1