algo — C++23 日本語リファレンス
GitHub

FenwickTree

クラス · フェニック木 (Fenwick Tree / BIT)

template <class T, bool RangeAdd = false>
struct FenwickTree;

概要

フェニック木

テンプレートパラメータ

名前 説明
RangeAdd true なら区間加算・区間総和（内部で BIT を 2 本保持）。 false なら点更新・区間総和（BIT 1 本、lower_bound/upper_bound あり）。

構築・破棄

名前 説明 計算量
(constructor) (1) 空のFenwick Treeを構築する
(2) 長さnの0列を構築する
(3) 列からFenwick Treeを構築する		 (1) $O(1)$
(2) $O(n)$
(3) RangeAddがfalseなら $O(n)$、trueなら $O(n\log n)$

メンバ関数

名前 説明 計算量
at k番目の値を返す $O(\log n)$
get k番目の値を返す $O(\log n)$
build 列の値を構築する RangeAddがfalseなら $O(n)$、trueなら $O(n\log n)$
set v[k] = val $O(\log n)$
add (1) v[k] += val
(2) v[a] … v[b - 1] += val		 $O(\log n)$
chmax chmax(v[k], val) $O(\log n)$
chmin chmin(v[k], val) $O(\log n)$
all_prod v[0] + … + v[n - 1] $O(\log n)$
prod (1) v[0] + … + v[k - 1]
(2) v[a] + … + v[b - 1]		 $O(\log n)$
all_sum v[0] + … + v[n - 1] $O(\log n)$
sum (1) v[0] + … + v[k - 1]
(2) v[a] + … + v[b - 1]		 $O(\log n)$
lower_bound (1) 接頭辞和がval以上となる最初の位置を返す
(2) kからの区間和がval以上となる最初の位置を返す		 $O(\log n)$
upper_bound (1) 接頭辞和がvalより大きくなる最初の位置を返す
(2) kからの区間和がvalより大きくなる最初の位置を返す		 $O(\log n)$

演算子

名前 説明 計算量
operator[] i番目の値を返す $O(\log n)$

メンバの詳細

(constructor)

// (1)
FenwickTree();

// (2)
FenwickTree(int n);

// (3)
template <class U>
FenwickTree(const std::vector<U> &v);

(1) 空のFenwick Treeを構築する

(2) 長さnの0列を構築する

(3) 列からFenwick Treeを構築する

add

// (1)
void add(int k, T val);

// (2)
void add(int a, int b, T val) requires RangeAdd;

(1) v[k] += val

(2) v[a] … v[b - 1] += val

prod

// (1)
T prod(int k) const;

// (2)
T prod(int a, int b) const;

(1) v[0] + … + v[k - 1]

(2) v[a] + … + v[b - 1]

sum

// (1)
T sum(int k) const;

// (2)
T sum(int a, int b) const;

(1) v[0] + … + v[k - 1]

(2) v[a] + … + v[b - 1]

lower_bound

// (1)
int lower_bound(T val) const requires(!RangeAdd);

// (2)
int lower_bound(int k, T val) const requires(!RangeAdd);

(1) 接頭辞和がval以上となる最初の位置を返す

(2) kからの区間和がval以上となる最初の位置を返す

upper_bound

// (1)
int upper_bound(T val) const requires(!RangeAdd);

// (2)
int upper_bound(int k, T val) const requires(!RangeAdd);

(1) 接頭辞和がvalより大きくなる最初の位置を返す

(2) kからの区間和がvalより大きくなる最初の位置を返す

参照