Binary Indexed Tree
(library/data-structure/bit.hpp)

• View this file on GitHub
• Last update: 2025-08-17 00:21:01+09:00
• Include: #include "library/data-structure/bit.hpp"

概要

Binary Indexed Tree (Fenwick Tree)

使い方

BIT<T, op, invop, e>(n)

• T : 要素の型
• op: 演算 (デフォルトは +)
• invop : 逆演算 (デフォルトは -)
• e : 単位元 (デフォルトは 0)
• n : 要素数
• bit.add(i, x) : i 番目の要素に x を加算する
• bit.sum(l, r) : [l, r) の要素の和を返す

Depends on

• library/_internal/modint-base.hpp
• 内部型 (library/_internal/types.hpp)

Required by

• Meissel–Lehmer Algorithm (library/math/meissel-lehmer.hpp)

Verified with

• tests/data-structure/bit/abc185-f.test.cpp
• tests/data-structure/bit/abc222-d.test.cpp
• tests/data-structure/bit/libchecker-rsq.test.cpp
• tests/data-structure/bit/libchecker-static.test.cpp
• tests/math/meissel-lehmer/libchecker.test.cpp

Code

#pragma once

#include <cassert>
#include <concepts>
#include <cstddef>
#include <functional>
#include <vector>
using namespace std;

#include "../_internal/types.hpp"

namespace asalib::ds {
  template<_internal::numeric_like T, auto op = plus<T>(), auto invop = minus<T>(), auto e = _internal::zero<T>>
    requires regular_invocable<decltype(op), T, T> && convertible_to<T, invoke_result_t<decltype(op), T, T>>
             && regular_invocable<decltype(invop), T, T> && convertible_to<T, invoke_result_t<decltype(invop), T, T>>
             && invocable<decltype(e)> && convertible_to<invoke_result_t<decltype(e)>, T>
  class BIT {
    public:
    BIT(): _n(0) {}
    explicit BIT(size_t n) {
      _n = n;
      data.reserve(n);
      data.resize(n, 0);
    }

    void add(size_t i, T x) {
      assert(i < _n);
      ++i;
      while (i <= _n) {
        data[i - 1] = op(data[i - 1], x);
        i += i & -i;
      }
    }

    T sum(const size_t l, const size_t r) const {
      assert(l <= r && r <= _n);
      return invop(_sum(r), _sum(l));
    }

    private:
    size_t _n;
    vector<T> data;
    T _sum(size_t i) const {
      T s = e();
      while (i > 0) {
        s = op(s, data[i - 1]);
        i -= i & -i;
      }
      return s;
    }
  };
}  // namespace asalib::ds

#line 2 "library/data-structure/bit.hpp"

#include <cassert>
#include <concepts>
#include <cstddef>
#include <functional>
#include <vector>
using namespace std;

#line 2 "library/_internal/types.hpp"

#line 4 "library/_internal/types.hpp"
using namespace std;

#line 2 "library/_internal/modint-base.hpp"

#include <type_traits>
using namespace std;

namespace asalib::_internal {
  class modint_base {};

  template<typename T>
  concept is_modint = is_base_of_v<modint_base, T>;
}  // namespace asalib::_internal
#line 7 "library/_internal/types.hpp"

namespace asalib::_internal {
  // ---------- concept definition ---------- //
  template<class T>
  concept integral_like = integral<T> || is_modint<T>;

  template<class T>
  concept floating_like = floating_point<T>;

  template<class T>
  concept numeric_like = integral_like<T> || floating_like<T>;

  // ---------- function definition ---------- //
  template<class T>
  T plus(T a, T b) { return a + b; }

  template<class T>
  T minus(T a, T b) { return a - b; }

  // ---------- constant definition ---------- //
  template<class T>
  T zero() { return 0; }
}  // namespace asalib::_internal
#line 11 "library/data-structure/bit.hpp"

namespace asalib::ds {
  template<_internal::numeric_like T, auto op = plus<T>(), auto invop = minus<T>(), auto e = _internal::zero<T>>
    requires regular_invocable<decltype(op), T, T> && convertible_to<T, invoke_result_t<decltype(op), T, T>>
             && regular_invocable<decltype(invop), T, T> && convertible_to<T, invoke_result_t<decltype(invop), T, T>>
             && invocable<decltype(e)> && convertible_to<invoke_result_t<decltype(e)>, T>
  class BIT {
    public:
    BIT(): _n(0) {}
    explicit BIT(size_t n) {
      _n = n;
      data.reserve(n);
      data.resize(n, 0);
    }

    void add(size_t i, T x) {
      assert(i < _n);
      ++i;
      while (i <= _n) {
        data[i - 1] = op(data[i - 1], x);
        i += i & -i;
      }
    }

    T sum(const size_t l, const size_t r) const {
      assert(l <= r && r <= _n);
      return invop(_sum(r), _sum(l));
    }

    private:
    size_t _n;
    vector<T> data;
    T _sum(size_t i) const {
      T s = e();
      while (i > 0) {
        s = op(s, data[i - 1]);
        i -= i & -i;
      }
      return s;
    }
  };
}  // namespace asalib::ds

Back to top page