Fenwick Tree
(data-structure/fenwick_tree.hpp)

• View this file on GitHub
• Last update: 2024-01-07 23:25:49+09:00
• Include: #include "data-structure/fenwick_tree.hpp"

Description

Fenwick tree，または binary indexed tree (BIT) は，可換モノイド $(T, \cdot, e)$ の列に対する一点更新と接頭辞和の取得を提供するデータ構造である．

セグメント木より制約が強く，操作が限られているが，実装が簡潔で定数倍速い．浮動小数点の演算をするときは，セグメント木よりも誤差が大きくなる傾向があるので注意が必要である．

空間計算量: $O(n)$

Operations

• FenwickTree(int n)
  • サイズnで要素がすべて単位元 $e$ の Fenwick tree を構築する
  • 時間計算量: $O(n)$
• T prefix_fold(int i)
  • 区間 $[0, i)$ の値を fold する
  • 時間計算量: $O(\log n)$
• void update(int i, T x)
  • $i$ 番目の要素を $x$ と演算した値に更新する
  • 時間計算量: $O(\log n)$
• int lower_bound(T x)
• int lower_bound(T x, Compare cmp)
  • cmp(prefix_fold(i), x) == false となる最初の $i$ を返す．そのような $i$ が存在しない場合は $n$ を返す．cmp を指定しない場合は < で比較される．列の単調性を仮定する．
  • 時間計算量: $O(\log n)$

Reference

• Binary Indexed Tree のはなし

Required by

• Lexicographic Index of Permutations (in Factorial Number System) (misc/permutation.hpp)
• Range Contour Aggregation (tree/range_contour_aggregation.hpp)

Verified with

• test/aoj/DSL_2_B.test.cpp
• test/yosupo/number_of_subsequences.test.cpp
• test/yosupo/static_range_inversions_query.test.cpp
• test/yosupo/vertex_add_range_contour_sum_on_tree.test.cpp
• test/yosupo/vertex_add_subtree_sum.hld.test.cpp

Code

#pragma once
#include <functional>
#include <vector>

template <typename M>
class FenwickTree {
    using T = M::T;

   public:
    FenwickTree() = default;
    explicit FenwickTree(int n) : n(n), data(n + 1, M::id()) {}

    T prefix_fold(int i) const {
        T ret = M::id();
        for (; i > 0; i -= i & -i) ret = M::op(ret, data[i]);
        return ret;
    }

    void update(int i, const T& x) {
        for (++i; i <= n; i += i & -i) data[i] = M::op(data[i], x);
    }

    int lower_bound(const T& x) const { return lower_bound(x, std::less<>()); }

    template <typename Compare>
    int lower_bound(const T& x, Compare cmp) const {
        if (!cmp(M::id(), x)) return 0;
        int k = 1;
        while (k * 2 <= n) k <<= 1;
        int i = 0;
        T v = M::id();
        for (; k > 0; k >>= 1) {
            if (i + k > n) continue;
            T nv = M::op(v, data[i + k]);
            if (cmp(nv, x)) {
                v = nv;
                i += k;
            }
        }
        return i + 1;
    }

   private:
    int n;
    std::vector<T> data;
};

#line 2 "data-structure/fenwick_tree.hpp"
#include <functional>
#include <vector>

template <typename M>
class FenwickTree {
    using T = M::T;

   public:
    FenwickTree() = default;
    explicit FenwickTree(int n) : n(n), data(n + 1, M::id()) {}

    T prefix_fold(int i) const {
        T ret = M::id();
        for (; i > 0; i -= i & -i) ret = M::op(ret, data[i]);
        return ret;
    }

    void update(int i, const T& x) {
        for (++i; i <= n; i += i & -i) data[i] = M::op(data[i], x);
    }

    int lower_bound(const T& x) const { return lower_bound(x, std::less<>()); }

    template <typename Compare>
    int lower_bound(const T& x, Compare cmp) const {
        if (!cmp(M::id(), x)) return 0;
        int k = 1;
        while (k * 2 <= n) k <<= 1;
        int i = 0;
        T v = M::id();
        for (; k > 0; k >>= 1) {
            if (i + k > n) continue;
            T nv = M::op(v, data[i + k]);
            if (cmp(nv, x)) {
                v = nv;
                i += k;
            }
        }
        return i + 1;
    }

   private:
    int n;
    std::vector<T> data;
};

Back to top page