BIT (Binary-Indexed-Tree)
(datastructure/binary-indexed-tree.hpp)

• View this file on GitHub
• Last update: 2021-04-15 20:24:09+09:00
• Include: #include "datastructure/binary-indexed-tree.hpp"
• Link: http://hos.ac/slides/20140319_bit.pdf

Verified with

• BITのテスト (test/aoj/DSL_2_B.bit.test.cpp)

Code

/**
 * @title BIT (Binary-Indexed-Tree)
 * @see http://hos.ac/slides/20140319_bit.pdf
 */
#include <cassert>
#include <vector>

template <class T>
struct BinaryIndexedTree {
  int n;
  std::vector<T> bit;
  BinaryIndexedTree(int n): n(n), bit(n+1) {}

  void build(const std::vector<T> &v) {
    for (int x = 1; x <= n; ++x) bit[x] = v[x-1];
    for (int x = 1; x < n; ++x) bit[x + (x & -x)] += bit[x];
  }

  void add(int a, T w) { // 0-indexed
    assert(0 <= a && a < n);
    for (int x = a+1; x <= n; x += x & -x) bit[x] += w; // 1-indexed
  }

  T sum(int a) { // [0, a)
    assert(0 <= a && a <= n);
    T ret = 0;
    for (int x = a; x > 0; x -= x & -x) ret += bit[x]; // 1-indexed
    return ret;
  }

  T sum(int l, int r) { return sum(r)-sum(l); } // 0-indexed, [l, r)
};

#line 1 "datastructure/binary-indexed-tree.hpp"
/**
 * @title BIT (Binary-Indexed-Tree)
 * @see http://hos.ac/slides/20140319_bit.pdf
 */
#include <cassert>
#include <vector>

template <class T>
struct BinaryIndexedTree {
  int n;
  std::vector<T> bit;
  BinaryIndexedTree(int n): n(n), bit(n+1) {}

  void build(const std::vector<T> &v) {
    for (int x = 1; x <= n; ++x) bit[x] = v[x-1];
    for (int x = 1; x < n; ++x) bit[x + (x & -x)] += bit[x];
  }

  void add(int a, T w) { // 0-indexed
    assert(0 <= a && a < n);
    for (int x = a+1; x <= n; x += x & -x) bit[x] += w; // 1-indexed
  }

  T sum(int a) { // [0, a)
    assert(0 <= a && a <= n);
    T ret = 0;
    for (int x = a; x > 0; x -= x & -x) ret += bit[x]; // 1-indexed
    return ret;
  }

  T sum(int l, int r) { return sum(r)-sum(l); } // 0-indexed, [l, r)
};

Back to top page