検証済み · 最終更新 2026-09-06 · GitHub

フェニック木 (Fenwick Tree / BIT)

lib/data_structure/fenwick_tree.hpp

概要

可換な加算に対する点更新・区間和を $O(\log n)$ で処理する。RangeAdd = true にすると内部で 2 本の Fenwick Tree を使い、区間加算・区間和を同じ計算量で処理する。

セグメント木より扱える演算は限られるが、必要なメモリと定数倍が小さい。

インクルード

#include "data_structure/fenwick_tree.hpp"

クラス

名前	説明
`FenwickTree`	フェニック木

例

#include <iostream>
#include <vector>
#include "data_structure/fenwick_tree.hpp"

int main() {
    std::vector<long long> a = {3, 1, 4, 1, 5};
    FenwickTree<long long> ft(a);
    ft.add(2, 10);                        // a[2] += 10
    std::cout << ft.sum(1, 4) << '\n';    // a[1] + a[2] + a[3]

    FenwickTree<long long, true> range_ft(5);
    range_ft.add(1, 4, 7);                // a[1], a[2], a[3] に 7 を加算
    std::cout << range_ft.sum(0, 5) << '\n';
}

出力

16
21

備考

lower_bound / upper_bound は RangeAdd = false のときだけ使える。各要素が非負で累積和が単調であることが前提で、条件を満たす位置がなければ n を返す。
lower_bound(k, val) と upper_bound(k, val) は探索基準に sum(k) を加え、添字 k 以降の累積増分を探索する。
T には加算だけでなく、区間和を差し引くための減算が必要。
空区間 sum(l, l) は T() を返す。

検証

このヘッダを使うライブラリ（1）

転倒数 lib/algorithm/inversion_number.hpp

検証プログラム（11）

test/aoj/alds1/inversion_number.test.cpp test/aoj/alds1/inversion_number.test.cpp
test/aoj/dsl/raq_rsq.test.cpp test/aoj/dsl/raq_rsq.test.cpp
test/aoj/dsl/rsq.test.cpp test/aoj/dsl/rsq.test.cpp
test/aoj/grl/range_query_on_tree.test.cpp test/aoj/grl/range_query_on_tree.test.cpp
test/aoj/grl/range_query_on_tree_2.test.cpp test/aoj/grl/range_query_on_tree_2.test.cpp
test/yosupo/data_structure/point_add_range_sum.test.cpp test/yosupo/data_structure/point_add_range_sum.test.cpp
test/yosupo/data_structure/static_range_inversions.test.cpp test/yosupo/data_structure/static_range_inversions.test.cpp
test/yosupo/tree/vertex_add_path_sum.test.cpp test/yosupo/tree/vertex_add_path_sum.test.cpp
test/yosupo/tree/vertex_add_subtree_sum.test.cpp test/yosupo/tree/vertex_add_subtree_sum.test.cpp
test/yukicoder/1209.test.cpp test/yukicoder/1209.test.cpp
test/yukicoder/2020.test.cpp test/yukicoder/2020.test.cpp

実装

#pragma once
#include <cassert>
#include <type_traits>
#include <variant>
#include <vector>

/// @file
/// @brief フェニック木 (Fenwick Tree / BIT)
/// @details 可換な加算に対する点更新・区間和を $O(\log n)$ で処理する。`RangeAdd = true` にすると
///          内部で 2 本の Fenwick Tree を使い、区間加算・区間和を同じ計算量で処理する。
/// @details セグメント木より扱える演算は限られるが、必要なメモリと定数倍が小さい。
/// @note `lower_bound` / `upper_bound` は `RangeAdd = false` のときだけ使える。
///       各要素が非負で累積和が単調であることが前提で、条件を満たす位置がなければ `n` を返す。
/// @note `lower_bound(k, val)` と `upper_bound(k, val)` は探索基準に `sum(k)` を加え、
///       添字 `k` 以降の累積増分を探索する。
/// @note `T` には加算だけでなく、区間和を差し引くための減算が必要。
/// @note 空区間 `sum(l, l)` は `T()` を返す。
/// @code
/// #include <iostream>
/// #include <vector>
/// #include "data_structure/fenwick_tree.hpp"
///
/// int main() {
///     std::vector<long long> a = {3, 1, 4, 1, 5};
///     FenwickTree<long long> ft(a);
///     ft.add(2, 10);                        // a[2] += 10
///     std::cout << ft.sum(1, 4) << '\n';    // a[1] + a[2] + a[3]
///
///     FenwickTree<long long, true> range_ft(5);
///     range_ft.add(1, 4, 7);                // a[1], a[2], a[3] に 7 を加算
///     std::cout << range_ft.sum(0, 5) << '\n';
/// }
/// @endcode

/// @brief フェニック木
/// @see http://hos.ac/slides/20140319_bit.pdf
/// @tparam RangeAdd true なら区間加算・区間総和（内部で BIT を 2 本保持）。
///                  false なら点更新・区間総和（BIT 1 本、`lower_bound`/`upper_bound` あり）。
template <class T, bool RangeAdd = false>
struct FenwickTree {
    /// @brief 空のFenwick Treeを構築する
    /// @complexity $O(1)$
    FenwickTree() : _size() {}

    /// @brief 長さnの0列を構築する
    /// @complexity $O(n)$
    FenwickTree(int n) : _size(n + 1), data(RangeAdd ? _size + 1 : _size) {
        if constexpr (RangeAdd) data2.assign(_size + 1, T());
    }
    /// @brief 列からFenwick Treeを構築する
    /// @complexity RangeAddがfalseなら $O(n)$、trueなら $O(n\log n)$
    template <class U>
    FenwickTree(const std::vector<U> &v) : FenwickTree((int)v.size()) {
        build(v);
    }

    /// @brief i番目の値を返す
    /// @complexity $O(\log n)$
    T operator[](int i) const { return sum(i, i + 1); }

    /// @brief k番目の値を返す
    /// @complexity $O(\log n)$
    T at(int k) const { return operator[](k); }

    /// @brief k番目の値を返す
    /// @complexity $O(\log n)$
    T get(int k) const { return operator[](k); }

    /// @brief 列の値を構築する
    /// @complexity RangeAddがfalseなら $O(n)$、trueなら $O(n\log n)$
    template <class U>
    void build(const std::vector<U> &v) {
        if constexpr (RangeAdd) {
            for (int i = 0, n = v.size(); i < n; ++i) add(i, v[i]);
        } else {
            for (int i = 0, n = v.size(); i < n; ++i) data[i + 1] = v[i];
            for (int i = 1; i < _size; ++i) {
                if (i + (i & -i) < _size) data[i + (i & -i)] += data[i];
            }
        }
    }

    /// @brief v[k] = val
    /// @complexity $O(\log n)$
    void set(int k, T val) { add(k, val - at(k)); }
    /// @brief v[k] += val
    /// @complexity $O(\log n)$
    void add(int k, T val) {
        if constexpr (RangeAdd) {
            add(k, k + 1, val);
        } else {
            assert(0 <= k && k < _size - 1);
            for (++k; k < _size; k += k & -k) data[k] += val;
        }
    }
    /// @brief v[a] ... v[b - 1] += val
    /// @complexity $O(\log n)$
    void add(int a, int b, T val)
    requires RangeAdd
    {
        assert(0 <= a && a <= b && b < _size);
        add_raw(data, a, -val * a);
        add_raw(data, b, val * b);
        add_raw(data2, a, val);
        add_raw(data2, b, -val);
    }
    /// @brief chmax(v[k], val)
    /// @complexity $O(\log n)$
    bool chmax(int k, T val) {
        if (at(k) >= val) return false;
        set(k, val);
        return true;
    }
    /// @brief chmin(v[k], val)
    /// @complexity $O(\log n)$
    bool chmin(int k, T val) {
        if (at(k) <= val) return false;
        set(k, val);
        return true;
    }

    /// @brief v[0] + ... + v[n - 1]
    /// @complexity $O(\log n)$
    T all_prod() const { return prod(_size - 1); }
    /// @brief v[0] + ... + v[k - 1]
    /// @complexity $O(\log n)$
    T prod(int k) const { return sum(k); }
    /// @brief v[a] + ... + v[b - 1]
    /// @complexity $O(\log n)$
    T prod(int a, int b) const { return sum(a, b); }
    /// @brief v[0] + ... + v[n - 1]
    /// @complexity $O(\log n)$
    T all_sum() const { return sum(_size - 1); }
    /// @brief v[0] + ... + v[k - 1]
    /// @complexity $O(\log n)$
    T sum(int k) const {
        assert(0 <= k && k < _size);
        if constexpr (RangeAdd) {
            return sum_raw(data, k) + sum_raw(data2, k) * k;
        } else {
            T res = T();
            for (; k > 0; k -= k & -k) res += data[k];
            return res;
        }
    }
    /// @brief v[a] + ... + v[b - 1]
    /// @complexity $O(\log n)$
    T sum(int a, int b) const {
        assert(0 <= a && a <= b && b < _size);
        if constexpr (RangeAdd) {
            return sum(b) - sum(a);
        } else {
            T res = T();
            while (a != b) {
                if (a < b) {
                    res += data[b];
                    b -= b & -b;
                } else {
                    res -= data[a];
                    a -= a & -a;
                }
            }
            return res;
        }
    }

    /// @brief 接頭辞和がval以上となる最初の位置を返す
    /// @complexity $O(\log n)$
    int lower_bound(T val) const
    requires(!RangeAdd)
    {
        assert(val >= 0);
        if (val == 0) return 0;
        int k = 1;
        while (k < _size) k <<= 1;
        int res = 0;
        for (; k > 0; k >>= 1) {
            if (res + k < _size && data[res + k] < val) val -= data[res += k];
        }
        return res;
    }
    /// @brief kからの区間和がval以上となる最初の位置を返す
    /// @complexity $O(\log n)$
    int lower_bound(int k, T val) const
    requires(!RangeAdd)
    {
        assert(val >= 0);
        return lower_bound(val + sum(k));
    }

    /// @brief 接頭辞和がvalより大きくなる最初の位置を返す
    /// @complexity $O(\log n)$
    int upper_bound(T val) const
    requires(!RangeAdd)
    {
        assert(val >= 0);
        int k = 1;
        while (k < _size) k <<= 1;
        int res = 0;
        for (; k > 0; k >>= 1) {
            if (res + k < _size && !(val < data[res + k])) val -= data[res += k];
        }
        return res;
    }
    /// @brief kからの区間和がvalより大きくなる最初の位置を返す
    /// @complexity $O(\log n)$
    int upper_bound(int k, T val) const
    requires(!RangeAdd)
    {
        assert(val >= 0);
        return upper_bound(val + sum(k));
    }

  private:
    static void add_raw(std::vector<T> &d, int k, T val) {
        for (++k; k < (int)d.size(); k += k & -k) d[k] += val;
    }
    static T sum_raw(const std::vector<T> &d, int k) {
        T res = T();
        for (; k > 0; k -= k & -k) res += d[k];
        return res;
    }

    int _size;
    std::vector<T> data;
    [[no_unique_address]] std::conditional_t<RangeAdd, std::vector<T>, std::monostate> data2;
};

bundled

#line 2 "lib/data_structure/fenwick_tree.hpp"
#include <cassert>
#include <type_traits>
#include <variant>
#include <vector>

/// @file
/// @brief フェニック木 (Fenwick Tree / BIT)
/// @details 可換な加算に対する点更新・区間和を $O(\log n)$ で処理する。`RangeAdd = true` にすると
///          内部で 2 本の Fenwick Tree を使い、区間加算・区間和を同じ計算量で処理する。
/// @details セグメント木より扱える演算は限られるが、必要なメモリと定数倍が小さい。
/// @note `lower_bound` / `upper_bound` は `RangeAdd = false` のときだけ使える。
///       各要素が非負で累積和が単調であることが前提で、条件を満たす位置がなければ `n` を返す。
/// @note `lower_bound(k, val)` と `upper_bound(k, val)` は探索基準に `sum(k)` を加え、
///       添字 `k` 以降の累積増分を探索する。
/// @note `T` には加算だけでなく、区間和を差し引くための減算が必要。
/// @note 空区間 `sum(l, l)` は `T()` を返す。
/// @code
/// #include <iostream>
/// #include <vector>
/// #include "data_structure/fenwick_tree.hpp"
///
/// int main() {
///     std::vector<long long> a = {3, 1, 4, 1, 5};
///     FenwickTree<long long> ft(a);
///     ft.add(2, 10);                        // a[2] += 10
///     std::cout << ft.sum(1, 4) << '\n';    // a[1] + a[2] + a[3]
///
///     FenwickTree<long long, true> range_ft(5);
///     range_ft.add(1, 4, 7);                // a[1], a[2], a[3] に 7 を加算
///     std::cout << range_ft.sum(0, 5) << '\n';
/// }
/// @endcode

/// @brief フェニック木
/// @see http://hos.ac/slides/20140319_bit.pdf
/// @tparam RangeAdd true なら区間加算・区間総和（内部で BIT を 2 本保持）。
///                  false なら点更新・区間総和（BIT 1 本、`lower_bound`/`upper_bound` あり）。
template <class T, bool RangeAdd = false>
struct FenwickTree {
    /// @brief 空のFenwick Treeを構築する
    /// @complexity $O(1)$
    FenwickTree() : _size() {}

    /// @brief 長さnの0列を構築する
    /// @complexity $O(n)$
    FenwickTree(int n) : _size(n + 1), data(RangeAdd ? _size + 1 : _size) {
        if constexpr (RangeAdd) data2.assign(_size + 1, T());
    }
    /// @brief 列からFenwick Treeを構築する
    /// @complexity RangeAddがfalseなら $O(n)$、trueなら $O(n\log n)$
    template <class U>
    FenwickTree(const std::vector<U> &v) : FenwickTree((int)v.size()) {
        build(v);
    }

    /// @brief i番目の値を返す
    /// @complexity $O(\log n)$
    T operator[](int i) const { return sum(i, i + 1); }

    /// @brief k番目の値を返す
    /// @complexity $O(\log n)$
    T at(int k) const { return operator[](k); }

    /// @brief k番目の値を返す
    /// @complexity $O(\log n)$
    T get(int k) const { return operator[](k); }

    /// @brief 列の値を構築する
    /// @complexity RangeAddがfalseなら $O(n)$、trueなら $O(n\log n)$
    template <class U>
    void build(const std::vector<U> &v) {
        if constexpr (RangeAdd) {
            for (int i = 0, n = v.size(); i < n; ++i) add(i, v[i]);
        } else {
            for (int i = 0, n = v.size(); i < n; ++i) data[i + 1] = v[i];
            for (int i = 1; i < _size; ++i) {
                if (i + (i & -i) < _size) data[i + (i & -i)] += data[i];
            }
        }
    }

    /// @brief v[k] = val
    /// @complexity $O(\log n)$
    void set(int k, T val) { add(k, val - at(k)); }
    /// @brief v[k] += val
    /// @complexity $O(\log n)$
    void add(int k, T val) {
        if constexpr (RangeAdd) {
            add(k, k + 1, val);
        } else {
            assert(0 <= k && k < _size - 1);
            for (++k; k < _size; k += k & -k) data[k] += val;
        }
    }
    /// @brief v[a] ... v[b - 1] += val
    /// @complexity $O(\log n)$
    void add(int a, int b, T val)
    requires RangeAdd
    {
        assert(0 <= a && a <= b && b < _size);
        add_raw(data, a, -val * a);
        add_raw(data, b, val * b);
        add_raw(data2, a, val);
        add_raw(data2, b, -val);
    }
    /// @brief chmax(v[k], val)
    /// @complexity $O(\log n)$
    bool chmax(int k, T val) {
        if (at(k) >= val) return false;
        set(k, val);
        return true;
    }
    /// @brief chmin(v[k], val)
    /// @complexity $O(\log n)$
    bool chmin(int k, T val) {
        if (at(k) <= val) return false;
        set(k, val);
        return true;
    }

    /// @brief v[0] + ... + v[n - 1]
    /// @complexity $O(\log n)$
    T all_prod() const { return prod(_size - 1); }
    /// @brief v[0] + ... + v[k - 1]
    /// @complexity $O(\log n)$
    T prod(int k) const { return sum(k); }
    /// @brief v[a] + ... + v[b - 1]
    /// @complexity $O(\log n)$
    T prod(int a, int b) const { return sum(a, b); }
    /// @brief v[0] + ... + v[n - 1]
    /// @complexity $O(\log n)$
    T all_sum() const { return sum(_size - 1); }
    /// @brief v[0] + ... + v[k - 1]
    /// @complexity $O(\log n)$
    T sum(int k) const {
        assert(0 <= k && k < _size);
        if constexpr (RangeAdd) {
            return sum_raw(data, k) + sum_raw(data2, k) * k;
        } else {
            T res = T();
            for (; k > 0; k -= k & -k) res += data[k];
            return res;
        }
    }
    /// @brief v[a] + ... + v[b - 1]
    /// @complexity $O(\log n)$
    T sum(int a, int b) const {
        assert(0 <= a && a <= b && b < _size);
        if constexpr (RangeAdd) {
            return sum(b) - sum(a);
        } else {
            T res = T();
            while (a != b) {
                if (a < b) {
                    res += data[b];
                    b -= b & -b;
                } else {
                    res -= data[a];
                    a -= a & -a;
                }
            }
            return res;
        }
    }

    /// @brief 接頭辞和がval以上となる最初の位置を返す
    /// @complexity $O(\log n)$
    int lower_bound(T val) const
    requires(!RangeAdd)
    {
        assert(val >= 0);
        if (val == 0) return 0;
        int k = 1;
        while (k < _size) k <<= 1;
        int res = 0;
        for (; k > 0; k >>= 1) {
            if (res + k < _size && data[res + k] < val) val -= data[res += k];
        }
        return res;
    }
    /// @brief kからの区間和がval以上となる最初の位置を返す
    /// @complexity $O(\log n)$
    int lower_bound(int k, T val) const
    requires(!RangeAdd)
    {
        assert(val >= 0);
        return lower_bound(val + sum(k));
    }

    /// @brief 接頭辞和がvalより大きくなる最初の位置を返す
    /// @complexity $O(\log n)$
    int upper_bound(T val) const
    requires(!RangeAdd)
    {
        assert(val >= 0);
        int k = 1;
        while (k < _size) k <<= 1;
        int res = 0;
        for (; k > 0; k >>= 1) {
            if (res + k < _size && !(val < data[res + k])) val -= data[res += k];
        }
        return res;
    }
    /// @brief kからの区間和がvalより大きくなる最初の位置を返す
    /// @complexity $O(\log n)$
    int upper_bound(int k, T val) const
    requires(!RangeAdd)
    {
        assert(val >= 0);
        return upper_bound(val + sum(k));
    }

  private:
    static void add_raw(std::vector<T> &d, int k, T val) {
        for (++k; k < (int)d.size(); k += k & -k) d[k] += val;
    }
    static T sum_raw(const std::vector<T> &d, int k) {
        T res = T();
        for (; k > 0; k -= k & -k) res += d[k];
        return res;
    }

    int _size;
    std::vector<T> data;
    [[no_unique_address]] std::conditional_t<RangeAdd, std::vector<T>, std::monostate> data2;
};