2️⃣

「バイナリインデックス付き木（BIT/Fenwick Tree）徹底解説!!：アルゴリズムの原理・数理的な構造・高速化の理由」

に公開
Python
アルゴリズム
dataengineering
datascience
binary
tech

記事本文ドラフト

はじめに

アルゴリズムやデータ構造の勉強をしていると、「区間和の高速計算」や「1点更新の高速化」がしばしば課題になります。
その代表的な解決策が「バイナリインデックス付き木（BIT: Binary Indexed Tree, または Fenwick Tree）」です。
本記事では、BITの数学的な背景から実装・応用例まで、学術的かつ直感的に分かりやすく解説します。

バイナリインデックス付き木（BIT）とは

BITは、配列上の「部分和（区間和）」や「要素の値変更」をO(logN)で処理できるデータ構造です。
競技プログラミングやデータベース、区間集計が多用される場面で必須の知識となっています。

利用シーン

  • 配列上での「区間の合計」「区間の個数」「区間の最大・最小」などを高速に計算したい場合
  • 配列要素の値の追加・削除・変更が頻繁に起こる場合

なぜBITは高速なのか？

〜区間和のための“木構造”の発想〜

BITの高速性のカギは、「2進数の性質を活かした“区間分割”」にあります。
配列を2進数的に区間分割し、各ノード（tree[i]）が“ある範囲の合計”だけを保持することで、
部分和や1点変更を最小限のジャンプで済ませることができます。

BITの内部構造

例：配列a[1]〜a[8]の場合

tree[i] 2進数 tree[i]が持つ区間
tree[1] 1 a[1]
tree[2] 10 a[1], a[2]
tree[3] 11 a[3]
tree[4] 100 a[1]〜a[4]
tree[5] 101 a[5]
tree[6] 110 a[5], a[6]
tree[7] 111 a[7]
tree[8] 1000 a[1]〜a[8]

各ノードは「自分の2進数で最下位ビットが立つ分だけ左へさかのぼった区間」を担当しています。

最下位ビットの役割

  • i & -i（iの2進数表現とその負の値のビットごとのAND）は、iの「最下位ビット」を抜き出す操作です。
  • これが「そのノードが持つ区間の長さ」を決定します。

sum・add の原理

  • 区間和(sum)
    sum(i)は、iまでの部分和を、
    「親ノード（より左の大きい区間）」へi -= i & -iでジャンプしながら累積
  • 1点更新(add)
    add(i, x)は、i以降の「自分を含む全ての親区間」へi += i & -iでジャンプしながら伝播

各ジャンプで「最下位ビット1個ずつ消していく/足していく」ことで、O(logN)で目的地に到達します。

数学的背景：区間分割の一意性

  • 2進数表現での「最下位ビットによる区間分割」は一意であり、
    どのノードも担当区間が重複も漏れもなく全体を分割しています。
  • これにより、「sum」も「add」も必要なノードだけを使って無駄なく集計・更新が可能となっています。

サンプル実装（Python）

class BIT:
    def __init__(self, n):
        self.N = n + 2
        self.tree = [0] * self.N

    def add(self, i, x):
        i += 1
        while i < self.N:
            self.tree[i] += x
            i += i & -i

    def sum(self, i):
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & -i
        return res

    def range_sum(self, l, r):
        return self.sum(r + 1) - self.sum(l)

まとめ・参考文献

  • BITは2進数区間分割によって、
    高速な区間集計と1点更新を両立させたアルゴリズムである。
  • その原理を理解すれば、さまざまな区間クエリ・集計問題に応用できる。
  • 学術的背景や数学的構造がしっかりしているからこそ、実用・競プロでこれだけ支持されている。

参考

  • P. M. Fenwick, "A New Data Structure for Cumulative Frequency Tables," Software: Practice and Experience, 24(3):327–336, 1994.
  • 「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」(蟻本)

おわりに

BITは一見難解に見えますが、
その「2進数での区間管理」の美しさを理解すれば、
「木構造・ビット演算・区間高速集計」の全てがクリアになります。
この記事が、あなたのアルゴリズム設計やコーディングの一助になれば幸いです。

Discussion