# BIT (Fenwick Tree) 一般化

[ABC410 G - Longest Chord Chain](https://atcoder.jp/contests/abc410/tasks/abc410_g) の fastest を見たら 1 点 chmax / prefix max の BIT が出てきた

- prefix prod
- 1 点変更の情報と区間の prod から変更後の区間の prod を計算できる

が満たされているモノイドなら良さそうだが，結局可換モノイドのことっぽい

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">abc266hのときに話題になっていました。<br>私も、可換モノイドだと prefix prod がとれるという定式化で実装しました。</p>&mdash; maspy (@maspy_stars) <a href="https://twitter.com/maspy_stars/status/1933950616868733421?ref_src=twsrc%5Etfw">June 14, 2025</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

何度か話題には上がっている話っぽいですね

## 一般化 BIT

BIT は可換モノイド `T` の列 $A = (a_0, a_1, \dots, a_{N-1})$ を持つ．

#### できる操作

- `T add(int i, T x)`
- $a_i \gets a_i \otimes x$ と変更する
- 計算量 : `op` の呼び出しを高々 $\lfloor\log N\rfloor+1$ 回
- `T` が可逆なら，1 点変更ができる
- `T sum(int r)`
- 前 $r$ 個のモノイド積 $a_0 \otimes a_1 \otimes \cdots \otimes a_{r-1}$ を返す
- 計算量 : `op` の呼び出しを高々 $\lfloor\log N\rfloor+1$ 回
- `T` が可逆なら，`sum(r) - sum(l)` で区間モノイド積が求められる
- `int max_right(function<bool(T)> f)`
- $f(a_0 \otimes a_1 \otimes \cdots \otimes a_{r-1})$ が `true` となる最大の $r$ を返す
- 計算量 : `f` と `op` の呼び出しを高々 $\lfloor\log N\rfloor+1$ 回

Segment Tree の下位互換だが，Segment Tree より時間・空間の定数倍が良い．

#### 用意する操作

- `T e()`
- 可換モノイド `T` の単位元を返す
- `T op(T a, T b)`
- モノイド積 $a \otimes b$ を返す
- 交換法則・結合法則を満たすこと

## 具体例

- 1 点加算 / 区間和クエリ
- `op` は `a + b`
- XOR とか，乗算とか，加算 mod M とか
- 1 点 chmax / prefix max クエリ
- `op` は `max(a, b)`
- LIS の DP とかで使える
- min / max とか，AND / OR とか，GCD / LCM とか，(最小値, 最小値の個数) とか

そもそも可換モノイドがそんなに種類ないですね