概要

Binary Indexed Tree（BIT）は、単点更新と区間クエリを効率的に処理できるデータ構造です。計算量 O(log N) で操作を実行可能であり、競技プログラミングやアルゴリズム最適化で広く利用されます。

構造と原理

BIT は 2 進数表現に基づく構造を利用します。任意の整数は複数の 2 のべき乗和で表せることから、配列要素をべき乗区間で管理します。lowbit 演算（x & -x で得られる最下位ビットの値）がキーポイントです。

基本操作

• 単点更新: 指定要素に値を加算
• 接頭辞和クエリ: 先頭から指定位置までの和を取得

コード例

class BIT {
private:
    vector<int> tree;
    int size;

    int lowbit(int x) { return x & -x; }

public:
    BIT(int n) : size(n), tree(n + 1) {}

    // 単点更新
    void update(int idx, int delta) {
        while (idx <= size) {
            tree[idx] += delta;
            idx += lowbit(idx);
        }
    }

    // 接頭辞和取得
    int query(int idx) {
        int result = 0;
        while (idx > 0) {
            result += tree[idx];
            idx -= lowbit(idx);
        }
        return result;
    }

    // 区間和取得
    int range_query(int l, int r) {
        return query(r) - query(l - 1);
    }
};

応用技法

逆数カウント

値域 BIT を用いて配列要素の出現回数を管理。要素 a[i] に対して、現在の BIT 内で a[i] より大きい値の出現数をクエリで取得。

int count_inversions(vector<int>& arr) {
    int n = arr.size();
    BIT bit(n);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += bit.query(n) - bit.query(arr[i]);
        bit.update(arr[i], 1);
    }
    return ans;
}

区間最大値クエリ

通常はセグメント木が使われますが、BIT でも log²N 計算量で実装可能。

class RangeMaxBIT {
private:
    vector<int> max_tree;
    vector<int> data;

    int lowbit(int x) { return x & -x; }

public:
    void update(int idx, int value) {
        data[idx] = value;
        int i = idx;
        while (i <= size) {
            max_tree[i] = max(data[i], max_tree[i]);
            i += lowbit(i);
        }
    }

    int query(int l, int r) {
        int result = INT_MIN;
        while (r >= l) {
            result = max(data[r], result);
            r--;
            while (r - lowbit(r) >= l) {
                result = max(max_tree[r], result);
                r -= lowbit(r);
            }
        }
        return result;
    }
};

差分配列管理

区間更新を単点クエリで処理する方法。差分配列 d[i] を BIT で管理。

// 区間 [l, r] への加算
bit.update(l, delta);
bit.update(r + 1, -delta);

// 単点クエリで元配列値取得
int value = bit.query(x);

応用例題

中央値クエリ

BIT と二分探索を組み合わせて動的中央値を取得。座圧（座標圧縮）が必要。

int find_median(BIT& bit, int max_val, int count) {
    int low = 1, high = max_val;
    while (low < high) {
        int mid = (low + high) / 2;
        if (bit.query(mid) > count / 2)
            high = mid;
        else
            low = mid + 1;
    }
    return low;
}

音声処理問題

スライド窓での最大値・最小値取得。BIT と K 番目クエリの組み合わせ。

int kth_smallest(BIT& bit, int k) {
    int result = 0, cnt = 0;
    for (int i = 20; i >= 0; i--) {
        int next = result + (1 << i);
        if (next > max_val) continue;
        if (cnt + bit.query(next) < k) {
            result = next;
            cnt += bit.query(next);
        }
    }
    return result + 1;
}

まとめ

BIT は柔軟性の高いデータ構造で、区間和計算、逆数カウント、動的計画法の高速化など幅広い応用が可能です。適切な変換を施すことで、最大値クエリや多次元拡張も実現できます。