趣旨

競技プログラミングで扱われる最も基本的なデータ構造の１つにBIT（Binary Indexed Tree／Fenwick tree／フェニック木）があります。

フェニック木を抽象化することで様々なことができますが、セグメント木でもできることが多いのでセグメント木ほどは注目されていなさそうです。

さっきたまたまtatyamさんの記事を読んで上級者もフェニック木の話題が気になっていることを知ったので、各種抽象化フェニック木にできることをまとめてみました。

twitterで見る限り逆元の存在や可換性が常に必要であるとされがちですが、ここではそれらを必ずしも課さずに説明していきます。

抽象化したフェニック木の具体的な実装自体は様々な解説で説明されていると思うので、ここではあくまでできることのまとめに徹しようと思います。

注意

上記の趣旨から、「一点加算更新とは何か」や「フェニック木内での二分探索とは何か」などフェニック木の多くの解説で説明されている内容は省略していきます。

この記事では区間加算に対応したフェニック木もフェニック木の一例として扱っています。何を持ってフェニック木と呼ぶかは人それぞれだと思いますので、区間加算に対応したフェニック木などの複数本のフェニック木の併用をもはやフェニック木とはみなさない人をこの記事は対象としていないことにご注意ください。

またここに記載する計算量の上界はあくまで著者（$p$進大好きbot）が把握している実装の上界に過ぎないので、同制約下での評価の最適性は保証しません。

なお筆者は案外色々乗るフェニック木に頼りすぎてセグメント木が習得できなくなる症状を抱えています。セグメント木を未習得の人は同じ症状を抱える危険性があるのでご注意ください。

目次

以下のフェニック木を扱っていきます。命名は一般的なものでなく、目次用に分かりやすいようにこの記事だけの命名をしました。

• BIT
  • 可換群BIT
  • 可換冪等モノイドBIT（区間$\max$BIT／区間$\min$BIT／区間$\gcd$BIT／区間$\textrm{lcm}$BIT）
  • 可換モノイドBIT
  • モノイドBIT
• 累積積BIT（累積$\max$BIT／累積$\min$BIT）
  • 可換モノイド累積積BIT
  • モノイド累積積BIT
• 区間加算BIT
  • $\mathbb{Z}$加群区間加算BIT

双対概念は扱っていません。双対概念は作用する側のマグマではなく作用によって得られる作用素の生成するモノイドがどのような性質（逆元の存在、可換性、冪等性）を満たすかを考えれば良いです。

代数構造の例

抽象化の話に入る前に代数構造をよく知らない人向けに、代数構造の例を挙げておきます。代数構造をよく知っている人はこの章を飛ばし、よく知らない人はこの章を読んで代数構造をよく知っている人になってもらいます。

可換群の例

以下環と言ったら可換環を指します。

• 固定した環とその加法の組
  • 整数全体の集合とその通常の加法の組
  • 固定した正整数$B$に対する、法$B$整数全体の集合とその通常の加法の組
    • $\{0,1\}$とそのXOR演算の組
    • 符号なし64bit整数全体の集合とその通常の加法の組
  • 有理数全体の集合とその通常の加法の組
  • 実数全体の集合とその通常の加法の組
  • 複素数全体の集合とその通常の加法の組
• 固定した環の乗法的可逆元全体の集合とその乗法の組
  • $\{-1,1\}$とその通常の乗法の組
  • 固定した正整数$B$に対する、$B$と互いに素な$B$未満の非負整数全体の集合とその法$B$乗法の組
  • $0$でない有理数全体の集合とその通常の乗法の組
  • $0$でない実数全体の集合とその通常の乗法の組
  • $0$でない複素数全体の集合とその通常の乗法の組
• 固定した環$R$と非負整数$L$に対する、$R$係数$L$次元ベクトル全体の集合とその通常の加法の組
  • 符号なし64bit整数全体の集合とそのXOR演算の組
  • 固定した集合$X$に対する、$X$の部分集合全体の集合とその対称差演算の組
• 固定した環$R$と非負整数$L,M$に対する、$R$係数$L \times M$行列全体の集合とその通常の加法の組
• 固定した環$R$に対する、$R$係数多項式全体の集合とその通常の加法の組
• 固定した環$R$に対する、$R$値数列全体の集合とその通常の加法の組
• 可換モノイドのグロタンディーク化
  • 与えられた配列の区間における$0$の出現頻度を表す整数（負も許容）とその通常の加法の組
  • 固定した素数$P$に対する、$P$未満の正整数と$P$進付値を表す整数（負も許容）の組全体の集合とその通常の演算の組

これらは全て可換群です。

可換冪等モノイドの例

• 固定した全順序集合とその$\max$演算の組
  • $\{0,1\}$とそのOR演算の組
  • 整数全体の集合とその$\max$演算の組
  • 有理数全体の集合とその$\max$演算の組
  • 実数全体の集合とその$\max$演算の組
  • 英小文字の集合とそのアルファベット順に関する$\max$演算の組
  • 英大文字の集合とそのアルファベット順に関する$\max$演算の組
  • 固定した全順序集合$P$に対する、$P$値有限列全体の集合とその辞書式順序に関する$\max$演算の組 - 文字列全体の集合とその辞書式順序に関する$\max$演算の組
  • 固定した非負整数$L$と全順序集合$P$に対する、長さ$L$の$P$値数列全体の集合とその辞書式順序に関する$\max$演算の組
    • 固定した非負整数$L$に対する、整数係数$L$次元ベクトル全体の集合とその辞書式順序に関する$\max$演算の組
• 固定した全順序集合とその$\min$演算の組
  • $\{0,1\}$とそのAND演算の組
  • 整数全体の集合とその$\min$演算の組
  • 有理数全体の集合とその$\min$演算の組
  • 実数全体の集合とその$\min$演算の組
  • 英小文字の集合とそのアルファベット順に関する$\min$演算の組
  • 英大文字の集合とそのアルファベット順に関する$\min$演算の組
  • 固定した全順序集合$P$に対する、$P$値有限列全体の集合とその辞書式順序に関する$\min$演算の組 - 文字列全体の集合とその辞書式順序に関する$\min$演算の組
  • 固定した非負整数$L$と全順序集合$P$に対する、長さ$L$の$P$値数列全体の集合とその辞書式順序に関する$\min$演算の組
    • 固定した非負整数$L$に対する、整数係数$L$次元ベクトル全体の集合とその辞書式順序に関する$\min$演算の組
• 固定した有界join半束$P$に対する、$P$値本質的有限列全体の集合とその各点join演算の組
  • 整数全体の集合とその$\gcd$演算の組
  • 整数全体の集合とその$\textrm{lcm}$演算の組
• 固定した非負整数$L$と有界join半束$P$に対する、長さ$L$の$P$値数列全体の集合とその各点join演算の組
  • 64bit整数全体の集合とそのOR演算の組
  • 64bit整数全体の集合とそのAND演算の組
  • 固定した集合$X$に対する、$X$の部分集合全体の集合とその$\cup$演算の組
  • 固定した集合$X$に対する、$X$の部分集合全体の集合とその$\cap$演算の組

これらは全て可換冪等モノイドです。なお可換冪等モノイドは有界join半束と等価です。

可換モノイドの例

• 環とその乗法の組
  • 整数全体の集合とその通常の乗法の組
  • 固定した正整数$B$に対する、法$B$整数全体の集合とその通常の乗法の組
  • 有理数全体の集合とその通常の乗法の組
  • 実数全体の集合とその通常の乗法の組
  • 複素数全体の集合とその通常の乗法の組
• 固定した環$R$に対する、$R$係数多項式全体の集合とその通常の乗法の組
• 固定した環$R$に対する、$R$値数列全体の集合とその各点乗法の組
• 固定した環$R$に対する、$R$値数列全体の集合とその畳み込み乗法の組

これらは全て可換モノイドです。もちろん可換群、可換冪等モノイドの例もまた可換モノイドです。

モノイドの例

• 固定した環$R$と非負整数$L,M$に対する、$R$係数$L \times M$行列全体の集合とその通常の乗法の組
• 固定した集合$X$に対する、写像$X \to X$全体の集合とその合成演算の組
• 固定したパラメータに対する、ローリングハッシュから自然に定まる代数構造
• 固定した配列と部分列の良い条件$P$に対する、$P$を満たす部分列の数え上げ問題から自然に定まる代数構造

これらは全てモノイドです。もちろん可換モノイドの例もまたモノイドです。

BIT

まずは抽象化する前のフェニック木^[1]のおさらいです。

通常のフェニック木の一点取得は区間取得で処理するため、そのままだと$\log_2 N$のオーダーで時間がかかりますが、フェニック木と通常の配列を両方管理することで、一点取得を$O(1)$で処理することも可能です。

フェニック木を用いた時の長さ$N$の整数値配列に対する時間計算量とその時間計算量は以下の通りです。

時間計算量

• デフォルト構築（$O(N)$）
• コピー構築（$O(N)$）
• ムーブ構築（$O(N)$）
• 一点加算更新（$O(\log_2 N)$）
• 一点代入更新（$O(\log_2 N)$）
• 一点取得（$O(\log_2 N)$または$O(1)$）
• 区間和取得（$O(\log_2 N)$）
• 二分探索（$O(\log_2 N)$）

これらは全てセグメント木も可能であるため競技プログラミングにおいてフェニック木はセグメント木の下位互換とみなされがちですが、フェニック木は時間計算量・空間計算量の定数倍が軽いという特徴を持ちます。

ちなみに競技プログラミングで問われることはほとんどないと思いますが、実はフェニック木には高速にできてセグメント木には高速にできないクエリ処理もあり、yukicoderのエイプリルフールコンでネタ問題として出題したことがあります。ぜひ解いてみてください。

• No.8112 区間和係数多項式？

空間計算量

長さ$N+1$の配列$1$本（と高速な一点取得を行う場合は長さ$N$の配列$1$本）で管理できるので、格納する整数値に必要なメモリを$c$と置くとおよそ$(N+1)c$（もしくは$(2N+1)c$）です。

累積積BIT

区間演算取得でなく左端からの累積演算取得のみを行う場合は、通常のフェニック木と同様に積や$\max$や$\min$を扱うことが可能です。

ただし一点代入更新は同じ実装だとうまくいかなくなるので、少し工夫が必要です。

ここでは用語を統一するため、積だけでなく$\max$や$min$も積や乗算と呼んでいくことにします。

時間計算量

• デフォルト構築（$O(N)$）
• コピー構築（$O(N)$）
• ムーブ構築（$O(N)$）
• 一点乗算更新（$O(\log_2 N)$）
• 一点代入更新（$O((\log_2 N)^2)$）
• 一点取得（$O(\log_2 N)$または$O(1)$）
• 累積積取得（$O(\log_2 N)$）
• 二分探索（$O(\log_2 N)$）

空間計算量

長さ$N+1$の配列$1$本（と高速な一点取得を行う場合は長さ$N$の配列$1$本）で管理できるので、格納する整数値に必要なメモリを$c$と置くとおよそ$(N+1)c$（もしくは$(2N+1)c$）です。

区間加算BIT

フェニック木を$2$本持ち、それぞれに階差数列と階差数列の微分などを管理することでフェニック木に機能を追加することができます。

代わりに二分探索は同じ実装だとうまくいかなくなります。もちろんフェニック木の外部で二分探索をすること自体は可能なので、$O((\log_2 N)^2)$での処理は可能です。

また通常の配列は高速に区間加算更新ができないため、通常の配列を併用することによる高速な一点取得もできなくなります。

時間計算量

• デフォルト構築（$O(N)$）
• コピー構築（$O(N)$）
• ムーブ構築（$O(N)$）
• 区間加算更新（$O(\log_2 N)$）
• 一点代入更新（$O(\log_2 N)$）
• 区間和取得（$O(\log_2 N)$）

空間計算量

長さ$N+1$の配列$2$本で管理できるので、格納する整数値に必要なメモリを$c$と置くとおよそ$(2N+2)c$です。

可換群BIT

次にフェニック木の抽象化を考えます。これまで整数の通常の加法を考えていましたが、特に工夫なく可換群に置き換えることが可能です。

ここからは時間計算量を説明する際、抽象化のインタフェースに指定されている演算が$O(1)$で処理されるとみなします。

ただし二分探索を行う場合は適当な条件を満たす全順序が必要です。

時間計算量

• デフォルト構築（$O(N)$）
• コピー構築（$O(N)$）
• ムーブ構築（$O(N)$）
• 一点加算更新（$O(\log_2 N)$）
• 一点代入更新（$O(\log_2 N)$）
• 一点取得（$O(\log_2 N)$または$O(1)$）
• 区間和取得（$O(\log_2 N)$）
• 二分探索（$O(\log_2 N)$）

空間計算量

長さ$N+1$の配列$1$本（と高速な一点取得を行う場合は長さ$N$の配列$1$本）で管理できるので、格納する可換群の要素に必要なメモリを$c$と置くとおよそ$(N+1)c$（もしくは$(2N+1)c$）です。

$p$進大好きライブラリ

https://github.com/p-adic/Mathematics/blob/master/SetTheory/DirectProduct/AffineSpace/BIT/

可換モノイド累積積BIT

区間演算取得でなく左端からの累積演算取得のみに特化したフェニック木は、特に工夫なく可換モノイドで抽象化できます。

ただし一点代入更新は同じ実装だとうまくいかなくなるので、低速化した上で少し工夫が必要です。

やはり二分探索を行う場合は適当な条件を満たす全順序が必要です。

時間計算量

• デフォルト構築（$O(N)$）
• コピー構築（$O(N)$）
• ムーブ構築（$O(N)$）
• 一点乗算更新（$O(\log_2 N)$）
• 一点代入更新（$O((\log_2 N)^2)$）
• 一点取得（$O(\log_2 N)$または$O(1)$）
• 累積積取得（$O(\log_2 N)$）
• 二分探索（$O(\log_2 N)$）

空間計算量

長さ$N+1$の配列$2$本（と高速な一点取得を行う場合は長さ$N$の配列$1$本）で管理できるので、格納するモノイドの要素に必要なメモリを$c$と置くとおよそ$(2N+2)c$（もしくは$O(3N+2)c$）です。

モノイド累積積BIT

区間演算取得でなく左端からの累積演算取得のみに特化したフェニック木は、高速な一点乗算更新を諦めれば一般のモノイドに抽象化することも可能です。一点乗算更新をしたい時は低速な一点代入更新で代用します。

やはり二分探索を行う場合は適当な条件を満たす全順序が必要です。

時間計算量

• デフォルト構築（$O(N)$）
• コピー構築（$O(N)$）
• ムーブ構築（$O(N)$）
• 一点代入更新（$O((\log_2 N)^2)$）
• 一点取得（$O(\log_2 N)$または$O(1)$）
• 累積積取得（$O(\log_2 N)$）
• 二分探索（$O(\log_2 N)$）

空間計算量

長さ$N+1$の配列$2$本（と高速な一点取得を行う場合は長さ$N$の配列$1$本）で管理できるので、格納するモノイドの要素に必要なメモリを$c$と置くとおよそ$(2N+2)c$（もしくは$O(3N+2)c$）です。

可換冪等モノイドBIT

可換群でなくとも、いわゆる左フェニック木と右フェニック木を$1$本ずつ持つことで可換冪等モノイドに抽象化することも可能です。^[2]

セグメント木と違って可換冪等モノイドに特化しているため、乗算が吸収できることがあることを活かした定数倍高速化ができることが特徴です。

やはり一点代入更新は同じ実装だとうまくいかなくなるので、少し工夫が必要です。

また高速な一点取得に対応させることも可能です。

やはり二分探索を行う場合は適当な条件を満たす全順序が必要です。

時間計算量

• デフォルト構築（$O(N)$）
• コピー構築（$O(N)$）
• ムーブ構築（$O(N)$）
• 一点乗算更新（$O(\log_2 N)$）
• 一点代入更新（$O((\log_2 N)^2)$）
• 一点取得（$O(\log_2 N)$または$O(1)$）
• 区間積取得（$O(\log_2 N)$）
• 二分探索（$O(\log_2 N)$）

空間計算量

長さ$N+1$の配列$2$本（と高速な一点取得を行う場合は長さ$N$の配列$1$本）で管理できるので、格納する可換冪等モノイドの要素に必要なメモリを$c$と置くとおよそ$(2N+2)c$（もしくは$O(3N+2)c$）です。

$p$進大好きライブラリ

https://github.com/p-adic/Mathematics/blob/master/SetTheory/DirectProduct/AffineSpace/BIT/IntervalMax

可換モノイドBIT

可換冪等モノイドでなくとも、乗算の扱いに気をつければ一般の可換モノイドに抽象化することも可能です。

冪等性などの特殊な条件に特化させていないため、セグメント木に勝る部分はほとんどありませんが、一応通常のフェニック木の章で述べた「フェニック木には高速にできてセグメント木には高速にできないクエリ処理」は依然として可能です。

やはり二分探索を行う場合は適当な条件を満たす全順序が必要です。

時間計算量

• デフォルト構築（$O(N)$）
• コピー構築（$O(N)$）
• ムーブ構築（$O(N)$）
• 一点乗算更新（$O(\log_2 N)$）
• 一点代入更新（$O((\log_2 N)^2)$）
• 一点取得（$O(\log_2 N)$または$O(1)$）
• 区間積取得（$O(\log_2 N)$）
• 二分探索（$O(\log_2 N)$）

空間計算量

長さ$N+1$の配列$2$本（と高速な一点取得を行う場合は長さ$N$の配列$1$本）で管理できるので、格納するモノイドの要素に必要なメモリを$c$と置くとおよそ$(2N+2)c$（もしくは$O(3N+2)c$）です。

モノイドBIT

可換モノイドでなくとも、高速な一点乗算更新を諦めれば一般のモノイドに抽象化することも可能です。一点乗算更新をしたい時は低速な一点代入更新で代用します。

相変わらずセグメント木に勝る部分はほとんどありませんが、一応通常のフェニック木の章で述べた「フェニック木には高速にできてセグメント木には高速にできないクエリ処理」は依然として可能です。

やはり二分探索を行う場合は適当な条件を満たす全順序が必要です。

時間計算量

• デフォルト構築（$O(N)$）
• コピー構築（$O(N)$）
• ムーブ構築（$O(N)$）
• 一点代入更新（$O((\log_2 N)^2)$）
• 一点取得（$O(\log_2 N)$または$O(1)$）
• 区間積取得（$O(\log_2 N)$）
• 二分探索（$O(\log_2 N)$）

空間計算量

長さ$N+1$の配列$2$本（と高速な一点取得を行う場合は長さ$N$の配列$1$本）で管理できるので、格納するモノイドの要素に必要なメモリを$c$と置くとおよそ$(2N+2)c$（もしくは$O(3N+2)c$）です。

$p$進大好きライブラリ

https://github.com/p-adic/Mathematics/blob/master/SetTheory/DirectProduct/AffineSpace/BIT/Monoid

$\mathbb{Z}$加群区間加算BIT

区間加算に対応したフェニック木は、残念ながら可換群のインタフェースで抽象化すると区間和取得が低速化してしまいます。

代わりに$\mathbb{Z}$加群のインタフェースで抽象化することで問題なく区間和取得を処理することが可能です。

可換群と$\mathbb{Z}$加群は（スカラー倍を標準的に定める操作とスカラー倍を忘れる操作により）等価な概念ですが、インタフェースとしては演算が異なることに注意しましょう。

これは例えば集合と基点付き集合が（点を標準的に追加する操作と基点を削除する操作により）等価な概念ですが前者には基点がなく後者には基点があることと同様です。操作で行き来できる意味で等価だからといって構造が同じわけではありません。

時間計算量

• デフォルト構築（$O(N)$）
• コピー構築（$O(N)$）
• ムーブ構築（$O(N)$）
• 区間加算更新（$O(\log_2 N)$）
• 一点代入更新（$O(\log_2 N)$）
• 区間和取得（$O(\log_2 N)$）

なお区間加算は$1$を値に取る定数との区間線形結合ともみなせ、特に工夫なく区間加算を一般の整数値配列との区間線形結合に一般化することも可能です。

空間計算量

長さ$N+1$の配列$2$本で管理できるので、格納するモノイドの要素に必要なメモリを$c$と置くとおよそ$(2N+2)c$です。

$p$進大好きライブラリ

https://github.com/p-adic/Mathematics/blob/master/SetTheory/DirectProduct/AffineSpace/BIT/IntervalAdd/

出典

1. P. M. Fenwick, A new data structure for cumulative frequency tables, Software: Practice and Experience, 1984, Vol. 24, Issue 3, pp. 327–336.
2. M. Dima, R. Ceterchi, Efficient Range Minimum Queries using Binary Indexed Trees, Olympiads in Informatics, 2015, Vol. 9, 39–44.