Fenwick Tree
(data_structure/fenwick_tree.cpp)

• View this file on GitHub
• Last update: 2020-03-11 22:42:07+09:00
• Link: https://scrapbox.io/data-structures/Fenwick_Tree

Depends on

• other/int_alias.cpp

Verified with

• test/fenwick_tree.test.cpp

Code

#include "other/int_alias.cpp"

#include <cassert>
#include <cstddef>
#include <vector>

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

public:
  using value_type = T;

private:
  std::vector<T> tree;

public:
  fenwick_tree() = default;

  explicit fenwick_tree(const usize size) : tree(size + 1, M::identity) {}

  bool empty() const { return size() == 0; }
  
  usize size() const { return tree.size() - 1; }

  T fold_prefix(usize last) const {
    assert(last <= size());
    T ret = M::identity;
    while (last != 0) {
      ret = M::operation(tree[last], ret);
      last &= last - 1;
    }
    return ret;
  }

  void add(usize index, const T value) {
    assert(index < size());
    index += 1;
    while (index < tree.size()) {
      tree[index] = M::operation(tree[index], value);
      index += index & ~index + 1;
    }
  }
};

/**
 * @brief Fenwick Tree
 * @see https://scrapbox.io/data-structures/Fenwick_Tree
 */

#line 2 "other/int_alias.cpp"

#include <cstddef>
#include <cstdint>

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
#line 2 "data_structure/fenwick_tree.cpp"

#include <cassert>
#line 5 "data_structure/fenwick_tree.cpp"
#include <vector>

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

public:
  using value_type = T;

private:
  std::vector<T> tree;

public:
  fenwick_tree() = default;

  explicit fenwick_tree(const usize size) : tree(size + 1, M::identity) {}

  bool empty() const { return size() == 0; }
  
  usize size() const { return tree.size() - 1; }

  T fold_prefix(usize last) const {
    assert(last <= size());
    T ret = M::identity;
    while (last != 0) {
      ret = M::operation(tree[last], ret);
      last &= last - 1;
    }
    return ret;
  }

  void add(usize index, const T value) {
    assert(index < size());
    index += 1;
    while (index < tree.size()) {
      tree[index] = M::operation(tree[index], value);
      index += index & ~index + 1;
    }
  }
};

/**
 * @brief Fenwick Tree
 * @see https://scrapbox.io/data-structures/Fenwick_Tree
 */

Back to top page