Binary Indexed Tree(Fenwick Tree)
(data-structure/binary-indexed-tree.hpp)
- View this file on GitHub
- Last update: 2021-12-20 22:10:59+09:00
- Include:
#include "data-structure/binary-indexed-tree.hpp"
Binary Indexed Tree
概要
Binary Indexed Tree(BIT, Fenwick Treeとも)とは、要素数$n$の数列に対して、値の一点加算と区間和の取得を$\mathrm{O}(\log n)$で行うことが出来るデータ構造である。実装がシンプルで定数倍が非常に軽い一方、Segment Treeと異なり逆元が存在しないと区間和が求められないという欠点もある。
また、imos法と併用することで区間加算と一点取得を$\mathrm{O}(\log N)$で行うこともできる。(実はimos法を使用しなくても実装を少し書き換えれば区間加算・一点取得BITは実現できるがここでは実装していない。)
使い方
-
BinaryIndexedTree<T>(size)
: 要素数$size+1$のBITを作成する。 -
add(k, x)
: k番目の要素にxを加算する。 -
operator[](k)
: k番目の要素を取得する。 -
sum(k)
: 区間[0, k]
の和を取得する。(閉区間に注意) -
sum(l, r)
: 区間[l, r]
の和を取得する。(閉区間に注意) -
imos(l, r, k)
: imos法を利用するとき、[l, r]
にkを加算する。(この時、一点取得はsum(k)
で行う。) -
lower_bound(w)
: 要素が全て非負の時、[0, k]
の区間和がw以上となるような最小のkを求める。 -
upper_bound(w)
: 要素が全て非負の時、[0, k]
の区間和がwよりも大きくなるような最小のkを求める。
Required by
Verified with
- verify/verify-aoj-dsl/aoj-dsl-2-b-bit.test.cpp
- verify/verify-aoj-dsl/aoj-dsl-2-e-imos.test.cpp
- verify/verify-aoj-dsl/aoj-dsl-2-g-bit.test.cpp
- verify/verify-yosupo-ds/yosupo-point-add-range-sum.test.cpp
- verify/verify-yosupo-ds/yosupo-point-add-rectangle-sum-abstruct-range-tree.test.cpp
- verify/verify-yosupo-ds/yosupo-static-range-inversion-query-2.test.cpp
- verify/verify-yosupo-ds/yosupo-static-range-inversions-query.test.cpp
- verify/verify-yosupo-ds/yosupo-vertex-add-path-sum-euler-tour.test.cpp
- verify/verify-yosupo-ds/yosupo-vertex-add-subtree-sum-dst-on-tree.test.cpp
- verify/verify-yosupo-ds/yosupo-vertex-add-subtree-sum-euler-tree.test.cpp
- verify/verify-yuki/yuki-1115.test.cpp