Fenwick Tree (Binary Indexed Tree, BIT)
(src/data-structure/fenwick-tree.hpp)

• View this file on GitHub
• Last update: 2023-07-30 00:54:52+09:00
• Include: #include "src/data-structure/fenwick-tree.hpp"

長さ $n$ の列 $(a_0, a_1, \cdots, a_{n-1})$ に対し

• $a_k$ への加算
• $a_l, a_{l+1}, \cdots, a_{r-1}$ の総和

を $O(\log n)$ で求めることが可能なデータ構造

コンストラクタ

(1) FenwickTree<T>(usize n)
(2) FenwickTree<T>(const std::vector<T> &as)

1. 列 $(a_0, a_1, \cdots a_{n-1})$ の全要素を T() で初期化する。
2. 列 $(a_0, a_1, \cdots a_{n-1})$ を $a_i = $ as[i] として初期化する。

制約

• $0 \leq n$

計算量

• $O(n)$

add

void add(usize k, const T &v)

$a_{k} \leftarrow a_{k} + v$ で更新を行う。

制約

• $0 \leq k < n$

計算量

• $O(\log n)$

sum

T sum(usize l, usize r) const

$a_{l} + a_{l+1} + \cdots + a_{r-1}$ を返す。

制約

• $0 \leq l \leq r \leq n$

計算量

• $O(\log n)$

Depends on

• rep 構造体 (src/cpp-template/header/rep.hpp)
• size alias (src/cpp-template/header/size-alias.hpp)

Verified with

• test/aoj/dsl_2_b/fenwick-tree.test.cpp
• unit-test/data-structure/fenwick-tree.test.cpp

Code

#pragma once

#include "src/cpp-template/header/rep.hpp"
#include "src/cpp-template/header/size-alias.hpp"

#include <cassert>
#include <vector>

namespace luz {

  template < typename T >
  class FenwickTree {
    usize n;
    std::vector< T > vals;

    T sum(usize k) const {
      T result(0);
      while (k > 0) {
        result += vals[k];
        k -= k & -k;
      }
      return result;
    }

   public:
    FenwickTree() = default;

    explicit FenwickTree(usize n): n(n), vals(n + 1, T()) {}

    explicit FenwickTree(const std::vector< T > &as)
        : n(as.size()),
          vals(as.size() + 1, T()) {
      for (usize i: rep(1, as.size() + 1)) {
        vals[i] = as[i - 1];
      }
      for (usize i: rep(1, as.size() + 1)) {
        usize j = i + (i & -i);
        if (j <= as.size()) {
          vals[j] += vals[i];
        }
      }
    }

    void add(usize k, const T &v) {
      assert(k < n);
      k++;
      while (k <= n) {
        vals[k] += v;
        k += k & -k;
      }
    }

    T sum(usize l, usize r) const {
      assert(l <= r and r <= n);
      return sum(r) - sum(l);
    }
  };

} // namespace luz

#line 2 "src/data-structure/fenwick-tree.hpp"

#line 2 "src/cpp-template/header/rep.hpp"

#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

} // namespace luz
#line 4 "src/cpp-template/header/rep.hpp"

#include <algorithm>

namespace luz {

  struct rep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        ++i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rep(const usize f, const usize l) noexcept
        : f(std::min(f, l)),
          l(l) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

  struct rrep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        --i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rrep(const usize f, const usize l) noexcept
        : f(l - 1),
          l(std::min(f, l) - 1) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

} // namespace luz
#line 5 "src/data-structure/fenwick-tree.hpp"

#include <cassert>
#include <vector>

namespace luz {

  template < typename T >
  class FenwickTree {
    usize n;
    std::vector< T > vals;

    T sum(usize k) const {
      T result(0);
      while (k > 0) {
        result += vals[k];
        k -= k & -k;
      }
      return result;
    }

   public:
    FenwickTree() = default;

    explicit FenwickTree(usize n): n(n), vals(n + 1, T()) {}

    explicit FenwickTree(const std::vector< T > &as)
        : n(as.size()),
          vals(as.size() + 1, T()) {
      for (usize i: rep(1, as.size() + 1)) {
        vals[i] = as[i - 1];
      }
      for (usize i: rep(1, as.size() + 1)) {
        usize j = i + (i & -i);
        if (j <= as.size()) {
          vals[j] += vals[i];
        }
      }
    }

    void add(usize k, const T &v) {
      assert(k < n);
      k++;
      while (k <= n) {
        vals[k] += v;
        k += k & -k;
      }
    }

    T sum(usize l, usize r) const {
      assert(l <= r and r <= n);
      return sum(r) - sum(l);
    }
  };

} // namespace luz

Back to top page