高頻度で単一点の更新と範囲合計の取得が必要なシステムにおいて、従来の配列構造は計算量の問題から実用性に欠ける。この課題を解決するため、Peter Fenwickによって提案されたフェニック木（Binary Indexed Tree）は、効率的な範囲演算を実現するデータ構造である。

基本概念と構造

フェニック木では各ノードが特定の区間の情報を保持し、二進数のビット演算を利用して階層関係を構築する。具体的には、インデックスiにおける最下位ビット(LSB)をi & -iで求め、その値が管理する区間の長さとなる。

主要操作の実装

class BinaryIndexTree {
private:
    vector<int> data;
    int size;

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

public:
    BinaryIndexTree(int n) : size(n), data(n + 1, 0) {}

    void update(int idx, int value) {
        for (int i = idx; i <= size; i += lowbit(i))
            data[i] += value;
    }

    int prefixSum(int idx) {
        int sum = 0;
        for (int i = idx; i > 0; i -= lowbit(i))
            sum += data[i];
        return sum;
    }

    int rangeSum(int left, int right) {
        return prefixSum(right) - prefixSum(left - 1);
    }
};

高速初期化手法

単純な要素追加による初期化はO(n log n)となるが、以下のように親ノードへの累積処理を行うことでO(n)で構築可能：

BinaryIndexTree(int n, const vector<int>& values) : size(n), data(n + 1, 0) {
    for (int i = 1; i <= n; ++i)
        data[i] = values[i - 1];
        
    for (int i = 1; i <= n; ++i) {
        int next = i + lowbit(i);
        if (next <= n)
            data[next] += data[i];
    }
}

範囲変更と範囲合計の同時サポート

差分配列を用いた2つのBITを管理することで、区間加算・区間合計クエリに対応できる：

class RangeBIT {
private:
    BinaryIndexTree bit1, bit2;

public:
    RangeBIT(int n) : bit1(n), bit2(n) {}

    void rangeUpdate(int l, int r, int delta) {
        bit1.update(l, delta);
        bit1.update(r + 1, -delta);
        bit2.update(l, l * delta);
        bit2.update(r + 1, -(r + 1) * delta);
    }

    int prefixQuery(int k) {
        return (k + 1) * bit1.prefixSum(k) - bit2.prefixSum(k);
    }

    int rangeQuery(int l, int r) {
        return prefixQuery(r) - prefixQuery(l - 1);
    }
};

極値検索の拡張

最大値や最小値のような非減算性情報に対しては、区間を適切に分割して探索を行う必要がある：

class MaxBIT {
private:
    vector<int> tree, source;
    int n;

public:
    MaxBIT(const vector<int>& vals) : n(vals.size()), tree(n + 1, INT_MIN), source(n + 1) {
        for (int i = 1; i <= n; ++i)
            update(i, vals[i - 1]);
    }

    void update(int pos, int val) {
        source[pos] = val;
        for (int i = pos; i <= n; i += lowbit(i)) {
            tree[i] = val;
            for (int j = 1; j < lowbit(i); j <<= 1)
                tree[i] = max(tree[i], tree[i - j]);
        }
    }

    int query(int l, int r) {
        int result = INT_MIN;
        while (r >= l) {
            if (r - lowbit(r) + 1 >= l) {
                result = max(result, tree[r]);
                r -= lowbit(r);
            } else {
                result = max(result, source[r]);
                --r;
            }
        }
        return result;
    }
};

多次元への拡張

二次元空間での範囲演算も同様の原理で実現できる：

class MatrixBIT {
private:
    vector<vector<int>> tree;
    int rows, cols;

public:
    MatrixBIT(int r, int c) : rows(r), cols(c), tree(r + 1, vector<int>(c + 1, 0)) {}

    void add(int x, int y, int delta) {
        for (int i = x; i <= rows; i += lowbit(i))
            for (int j = y; j <= cols; j += lowbit(j))
                tree[i][j] += delta;
    }

    int prefixSum(int x, int y) {
        int sum = 0;
        for (int i = x; i > 0; i -= lowbit(i))
            for (int j = y; j > 0; j -= lowbit(j))
                sum += tree[i][j];
        return sum;
    }

    int rangeSum(int x1, int y1, int x2, int y2) {
        return prefixSum(x2, y2) - prefixSum(x1 - 1, y2) 
               - prefixSum(x2, y1 - 1) + prefixSum(x1 - 1, y1 - 1);
    }
};