フェニック木（Binary Indexed Tree, BIT）は、主に数列の prefix sum（接頭辞和）を効率的に管理・計算するために設計されたデータ構造です。セグメント木と比較して実装が簡潔であり、定数倍の計算コストが低いため、頻繁な更新とクエリが発生する箇所で広く利用されています。本記事では、基本的な1次元の構造から、差分を利用した区間更新、および2次元への拡張について解説します。

基本的な1次元フェニック木

このデータ構造は、配列の各要素に対して、そのインデックスの2進表現に基づいて特定の区間の和を管理します。特定のインデックス i が管理する区間の長さは、lowbit(i)（2進表現における最下位の1が表す値）によって決まります。

演算の定義

• 単点更新: 配列の特定の要素の値を変更する。
• 区間クエリ: 配列の連続した区間（例：[l, r]）の和を求める。

実装の仕組み

配列を tree とします。lowbit(x) は x & -x で計算できます。

• 更新: インデックス i の値を増やす場合、i およびその親ノードに相当する i + lowbit(i) 以下のインデックスを順次更新します。
• クエリ: 1 から i までの和を求める場合、i から始めて tree[i] を加算し、インデックスを i - lowbit(i) で更新することを繰り返します。[l, r] の区間和は、sum(r) - sum(l-1) で求められます。

これらの操作は1回あたり O(log n) の時間複雑度で完了します。

#include <vector>

class FenwickTree {
private:
    std::vector<long long> data;
    size_t capacity;

    // 最下位ビットを取得
    int lowbit(int x) const {
        return x & -x;
    }

public:
    FenwickTree(size_t n) : capacity(n), data(n + 1, 0) {}

    // インデックスidxの値にvalを加算（単点更新）
    void update(int idx, long long val) {
        while (idx <= capacity) {
            data[idx] += val;
            idx += lowbit(idx);
        }
    }

    // 先頭からidxまでの累積和を計算
    long long prefix_sum(int idx) {
        long long res = 0;
        while (idx > 0) {
            res += data[idx];
            idx -= lowbit(idx);
        }
        return res;
    }

    // 区間[l, r]の合計を取得
    long long range_query(int l, int r) {
        return prefix_sum(r) - prefix_sum(l - 1);
    }
};

差分構造による区間更新と単点取得

フェニック木を差分配列と組み合わせることで、「区間更新」と「単点取得」という逆のパターンを効率的に処理できます。

手法

元の配列を A、差分配列を D とします（A[i] = D[1] + ... + D[i]）。

• 区間更新 [l, r] に値 v を加算: 差分配列の性質上、D[l] に v を加算し、D[r+1] から v を減算すれば、その区間外には影響を与えずに区間内の累積和を増加させられます。これはフェニック木上での2回の単点更新として処理できます。
• 単点取得 A[i]: これは差分配列の先頭から i までの和に等しいため、フェニック木の標準的な累積和クエリとして処理できます。

class DiffFenwick {
private:
    std::vector<int> bit;
    int n;

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

public:
    DiffFenwick(int size) : n(size), bit(size + 2, 0) {}

    // 区間 [l, r] に val を加算
    void range_update(int l, int r, int val) {
        internal_update(l, val);
        internal_update(r + 1, -val);
    }

    // ポイント idx の現在の値を取得
    int point_query(int idx) {
        int res = 0;
        while (idx > 0) {
            res += bit[idx];
            idx -= lowbit(idx);
        }
        return res;
    }

private:
    void internal_update(int idx, int delta) {
        while (idx <= n + 1) {
            bit[idx] += delta;
            idx += lowbit(idx);
        }
    }
};

二次元フェニック木

フェニック木は2次元平面上の行列データに拡張できます。ここでは、単一の要素の更新と、部分行列（例：原点から (x, y) の範囲）の和のクエリを扱います。

構造と計算量

データ構造は2次元配列であり、各次元においてフェニック木のロジックを適用します。更新とクエリの両方で2重ループが必要となるため、時間計算量は O(log^2 n) となります。

class FenwickTree2D {
    int n, m;
    std::vector<std::vector<int>> tree;

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

public:
    FenwickTree2D(int size_x, int size_y) : n(size_x), m(size_y) {
        tree.assign(n + 1, std::vector<int>(m + 1, 0));
    }

    // ポイント (x, y) に val を加算
    void add_point(int x, int y, int val) {
        for (int i = x; i <= n; i += lowbit(i)) {
            for (int j = y; j <= m; j += lowbit(j)) {
                tree[i][j] += val;
            }
        }
    }

    // 原点 (1,1) から (x, y) までの矩形領域の合計を取得
    int query_prefix(int x, int y) {
        int result = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {
            for (int j = y; j > 0; j -= lowbit(j)) {
                result += tree[i][j];
            }
        }
        return result;
    }

    // 任意の部分行列 [x1, y1] から [x2, y2] の合計（包含除外原理を利用）
    int query_rect(int x1, int y1, int x2, int y2) {
        return query_prefix(x2, y2) 
             - query_prefix(x1 - 1, y2) 
             - query_prefix(x2, y1 - 1) 
             + query_prefix(x1 - 1, y1 - 1);
    }
};