セグメント木とフェンウィック木（BIT）はどのようにして高速な範囲クエリをサポートしますか？

Question

Accepted Answer

**セグメント木**と**フェンウィック木**（Binary Indexed Tree、BIT）はどちらも、**範囲クエリ**（例えば`[l, r]`の合計）と**ポイント更新**を**O(log n)**で処理します。これは単純なスキャンのO(n)やプレフィックス合計配列の更新O(n)と比較して高速です。

## これらが解く問題

```text
Array + many "sum of range [l,r]" and "update index i" calls:
  naive prefix sums: query O(1) but UPDATE is O(n)
  segment/Fenwick:   query O(log n) AND update O(log n)
```

## フェンウィック木（BIT）— コンパクトでエレガント

```python
class Fenwick:
    def __init__(self, n):
        self.t = [0]*(n+1)
    def update(self, i, delta):        # O(log n)
        i += 1
        while i < len(self.t):
            self.t[i] += delta
            i += i & (-i)              # jump to next responsible node
    def prefix(self, i):               # sum of [0..i], O(log n)
        i += 1; s = 0
        while i > 0:
            s += self.t[i]
            i -= i & (-i)
        return s
    def range_sum(self, l, r):
        return self.prefix(r) - self.prefix(l-1)
```

## セグメント木 — より汎用的

セグメント木はバイナリツリーの各配列セグメントに対する集計を格納し、**任意の結合法則を満たす操作**（合計、最小値、最大値、最大公約数）をサポートします。遅延伝播を使用すれば、**範囲更新**もサポートします。

```text
        [0..7] sum
       /          \
   [0..3]         [4..7]
   /    \         /    \
 [0..1][2..3]  [4..5][6..7]   ... down to single elements
```

## 比較

| | フェンウィック（BIT） | セグメント木 |
|---|---|---|
| クエリ / 更新 | O(log n) | O(log n) |
| 空間 | O(n) | O(2n) |
| 操作 | 合計（可逆） | 任意の結合法則を満たす操作 |
| 範囲更新 | より難しい | 簡単（遅延伝播） |
| コードサイズ | 非常に小さい | より大きい |

## なぜ重要なのか

これらの構造により、「値を更新してから範囲の集計をクエリする」操作が高速になります。競技プログラミング、分析ウィンドウ、区間問題に不可欠です。

どちらを選ぶかは、トレードオフです。フェンウィック木は合計に対して小さく高速ですが、セグメント木は最小値/最大値/範囲更新ワークロードに対してより柔軟です。

	フェンウィック（BIT）	セグメント木
クエリ / 更新	O(log n)	O(log n)
空間	O(n)	O(2n)
操作	合計（可逆）	任意の結合法則を満たす操作
範囲更新	より難しい	簡単（遅延伝播）
コードサイズ	非常に小さい	より大きい