0Pricing
Coding Interview Prep · レッスン

累積和のための Fenwick Tree

一点更新と累積クエリを log n で行います

「累積和のための Fenwick Tree」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

累積和配列が破綻する理由

通常の累積和配列なら区間の合計をすぐに求められますが、1か所更新するだけで再構築が必要です。更新が多いと、処理が遅くなります。⏱️

Fenwick tree の登場

Fenwick tree（BIT）は、点更新と累積クエリの両方を O(log n) で処理できます。動的な累積値を扱うときの定番です。

1始まりの設計

Fenwick tree は 1 始まりの配列で動作します。インデックス 0 を使わない番兵にすることで、実際のデータはすべて位置 1から始まります。

tree = [0] * (n + 1)

最下位のセットビットの力

各インデックスは値のブロックを担当します。ブロックのサイズはi & -i、つまり i の最下位のセットビットに等しくなります。この1つの仕組みが木全体を支えています。

lowbit = i & -i

1か所を更新する

位置 i に値を加えるには、各ステップでlowbitの分だけ前へ進み、i を含むすべてのブロックを更新します。

while i <= n:
    tree[i] += delta
    i += i & -i

累積和をクエリする

最初の i 個の値を合計するには、各ステップでlowbitを引きながら後ろへ進み、0 に到達するまで繰り返します。

s = 0
while i > 0:
    s += tree[i]
    i -= i & -i

どちらのループも対数時間

各ループは反復するたびに1ビットをオフにするため、実行回数は最大でもlog n回です。これが、更新とクエリの両方を高速に保てる理由です。

2つの累積和から区間和を求める

l から r までの合計が必要ですか？静的な累積和配列と同じように、prefix(r) minus prefix(l-1)を計算します。今回は更新も低コストです。

range_sum = query(r) - query(l - 1)

木を構築する

最も簡単な構築方法は、初期値ごとにupdateを呼び出すことです。計算量は O(n log n) で、ほとんどの競技プログラミングに十分な速さです。

for i, v in enumerate(a, 1):
    update(i, v)

小さなメモリ使用量

Fenwick tree に必要なのは、サイズ n+1 の配列1つだけです。このコンパクトなメモリ使用量も、競技プログラミングで広く使われる理由の1つです。💾

BIT を使う場面

点更新と累積和または区間和のクエリを交互に処理するなら、Fenwick tree を選びます。短く実装でき、これに勝る方法はなかなかありません。

確認問題

ループがどのように移動するかを確認しましょう。

振り返り：BIT の基本

Fenwick treeを学びました。1 始まりで、i & -i を利用し、点更新と累積クエリをどちらも O(log n) で処理します。次はこれを使って転倒数を数えます。🎯

よくある質問

「累積和のための Fenwick Tree」レッスンは無料ですか？

はい。「累積和のための Fenwick Tree」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「累積和のための Fenwick Tree」で何を学びますか？

一点更新と累積クエリを log n で行います ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。

「累積和のための Fenwick Tree」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 累積和のための Fenwick Tree
  2. BIT による転倒数
  3. セグメント木: 構築とクエリ
  4. 範囲更新の遅延伝播
← Coding Interview Prepに戻る