Binary Indexed Tree(Fenwick Tree)
(data-structure/binary-indexed-tree.hpp)

• View this file on GitHub
• Last update: 2021-12-20 22:10:59+09:00
• Include: #include "data-structure/binary-indexed-tree.hpp"

Binary Indexed Tree

概要

Binary Indexed Tree(BIT, Fenwick Treeとも)とは、要素数$n$の数列に対して、値の一点加算と区間和の取得を$\mathrm{O}(\log n)$で行うことが出来るデータ構造である。実装がシンプルで定数倍が非常に軽い一方、Segment Treeと異なり逆元が存在しないと区間和が求められないという欠点もある。

また、imos法と併用することで区間加算と一点取得を$\mathrm{O}(\log N)$で行うこともできる。(実はimos法を使用しなくても実装を少し書き換えれば区間加算・一点取得BITは実現できるがここでは実装していない。)

使い方

• BinaryIndexedTree<T>(size): 要素数$size+1$のBITを作成する。
• add(k, x): k番目の要素にxを加算する。
• operator[](k): k番目の要素を取得する。
• sum(k): 区間[0, k]の和を取得する。(閉区間に注意)
• sum(l, r): 区間[l, r]の和を取得する。(閉区間に注意)
• imos(l, r, k): imos法を利用するとき、[l, r]にkを加算する。(この時、一点取得はsum(k)で行う。)
• lower_bound(w): 要素が全て非負の時、[0, k]の区間和がw以上となるような最小のkを求める。
• upper_bound(w): 要素が全て非負の時、[0, k]の区間和がwよりも大きくなるような最小のkを求める。

Required by

• data-structure-2d/rectangle-add-rectangle-sum.hpp
• data-structure/range-sum-range-add-bit.hpp
• dp/inversion-counting.hpp

Verified with

• verify/verify-aoj-dsl/aoj-dsl-2-b-bit.test.cpp
• verify/verify-aoj-dsl/aoj-dsl-2-e-imos.test.cpp
• verify/verify-aoj-dsl/aoj-dsl-2-g-bit.test.cpp
• verify/verify-yosupo-ds/yosupo-point-add-range-sum.test.cpp
• verify/verify-yosupo-ds/yosupo-point-add-rectangle-sum-abstruct-range-tree.test.cpp
• verify/verify-yosupo-ds/yosupo-static-range-inversion-query-2.test.cpp
• verify/verify-yosupo-ds/yosupo-static-range-inversions-query.test.cpp
• verify/verify-yosupo-ds/yosupo-static-rectangle-add-rectangle-sum.test.cpp
• verify/verify-yosupo-ds/yosupo-vertex-add-path-sum-euler-tour.test.cpp
• verify/verify-yosupo-ds/yosupo-vertex-add-subtree-sum-dst-on-tree.test.cpp
• verify/verify-yosupo-ds/yosupo-vertex-add-subtree-sum-euler-tree.test.cpp
• verify/verify-yuki/yuki-1115.test.cpp

Code

#pragma once

template <typename T>
struct BinaryIndexedTree {
  int N;
  vector<T> data;

  BinaryIndexedTree() = default;

  BinaryIndexedTree(int size) { init(size); }

  void init(int size) {
    N = size + 2;
    data.assign(N + 1, {});
  }

  // get sum of [0,k]
  T sum(int k) const {
    if (k < 0) return T{};  // return 0 if k < 0
    T ret{};
    for (++k; k > 0; k -= k & -k) ret += data[k];
    return ret;
  }

  // getsum of [l,r]
  inline T sum(int l, int r) const { return sum(r) - sum(l - 1); }

  // get value of k
  inline T operator[](int k) const { return sum(k) - sum(k - 1); }

  // data[k] += x
  void add(int k, T x) {
    for (++k; k < N; k += k & -k) data[k] += x;
  }

  // range add x to [l,r]
  void imos(int l, int r, T x) {
    add(l, x);
    add(r + 1, -x);
  }

  // minimize i s.t. sum(i) >= w
  int lower_bound(T w) {
    if (w <= 0) return 0;
    int x = 0;
    for (int k = 1 << __lg(N); k; k >>= 1) {
      if (x + k <= N - 1 && data[x + k] < w) {
        w -= data[x + k];
        x += k;
      }
    }
    return x;
  }

  // minimize i s.t. sum(i) > w
  int upper_bound(T w) {
    if (w < 0) return 0;
    int x = 0;
    for (int k = 1 << __lg(N); k; k >>= 1) {
      if (x + k <= N - 1 && data[x + k] <= w) {
        w -= data[x + k];
        x += k;
      }
    }
    return x;
  }
};

/**
 * @brief Binary Indexed Tree(Fenwick Tree)
 * @docs docs/data-structure/binary-indexed-tree.md
 */

#line 2 "data-structure/binary-indexed-tree.hpp"

template <typename T>
struct BinaryIndexedTree {
  int N;
  vector<T> data;

  BinaryIndexedTree() = default;

  BinaryIndexedTree(int size) { init(size); }

  void init(int size) {
    N = size + 2;
    data.assign(N + 1, {});
  }

  // get sum of [0,k]
  T sum(int k) const {
    if (k < 0) return T{};  // return 0 if k < 0
    T ret{};
    for (++k; k > 0; k -= k & -k) ret += data[k];
    return ret;
  }

  // getsum of [l,r]
  inline T sum(int l, int r) const { return sum(r) - sum(l - 1); }

  // get value of k
  inline T operator[](int k) const { return sum(k) - sum(k - 1); }

  // data[k] += x
  void add(int k, T x) {
    for (++k; k < N; k += k & -k) data[k] += x;
  }

  // range add x to [l,r]
  void imos(int l, int r, T x) {
    add(l, x);
    add(r + 1, -x);
  }

  // minimize i s.t. sum(i) >= w
  int lower_bound(T w) {
    if (w <= 0) return 0;
    int x = 0;
    for (int k = 1 << __lg(N); k; k >>= 1) {
      if (x + k <= N - 1 && data[x + k] < w) {
        w -= data[x + k];
        x += k;
      }
    }
    return x;
  }

  // minimize i s.t. sum(i) > w
  int upper_bound(T w) {
    if (w < 0) return 0;
    int x = 0;
    for (int k = 1 << __lg(N); k; k >>= 1) {
      if (x + k <= N - 1 && data[x + k] <= w) {
        w -= data[x + k];
        x += k;
      }
    }
    return x;
  }
};

/**
 * @brief Binary Indexed Tree(Fenwick Tree)
 * @docs docs/data-structure/binary-indexed-tree.md
 */

Back to top page