test/unittest/binary-indexed-trees.test.cpp

• View this file on GitHub
• Last update: 2026-08-04 11:55:02+00:00

Depends on

• Abstract Binary Indexed Tree(抽象化BIT) (structure/others/abstract-binary-indexed-tree.hpp)
• Binary Indexed Tree (structure/others/binary-indexed-tree.hpp)

Code

// competitive-verifier: STANDALONE

#include <algorithm>
#include <cassert>
#include <random>
#include <vector>

#include "../../structure/others/abstract-binary-indexed-tree.hpp"
#include "../../structure/others/binary-indexed-tree.hpp"

int main() {
  {
    BinaryIndexedTree<int> tree(std::vector<int>{1, 2, 3, 4});
    assert(tree.prod(0) == 0);
    assert(tree.prod(4) == 10);
    assert(tree.prod(1, 3) == 5);
    assert(tree.lower_bound(1) == 0);
    assert(tree.lower_bound(4) == 2);
    assert(tree.lower_bound(11) == 4);
    assert(tree.upper_bound(0) == 0);
    assert(tree.upper_bound(3) == 2);
    assert(tree.upper_bound(10) == 4);
  }

  std::mt19937 rng(123456789);
  for (int n = 1; n <= 100; n++) {
    std::vector<int> values(n);
    BinaryIndexedTree<int> sum(n);
    for (int iteration = 0; iteration < 500; iteration++) {
      int index = rng() % n;
      int delta = rng() % 10;
      values[index] += delta;
      sum.apply(index, delta);

      int left = rng() % (n + 1);
      int right = rng() % (n + 1);
      if (left > right) std::swap(left, right);
      int expected = 0;
      for (int i = left; i < right; i++) expected += values[i];
      assert(sum.prod(left, right) == expected);
    }

    auto maximum = get_abstract_binary_indexed_tree(
        values, [](int a, int b) { return std::max(a, b); }, -1);
    int expected = -1;
    for (int right = 0; right <= n; right++) {
      if (right > 0) expected = std::max(expected, values[right - 1]);
      assert(maximum.prod(right) == expected);
    }
  }
}

#line 1 "test/unittest/binary-indexed-trees.test.cpp"
// competitive-verifier: STANDALONE

#include <algorithm>
#include <cassert>
#include <random>
#include <vector>

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

#line 5 "structure/others/abstract-binary-indexed-tree.hpp"

/**
 * @brief Abstract Binary Indexed Tree(抽象化BIT)
 */
template <typename T, typename F>
struct AbstractBinaryIndexedTree {
 private:
  int n;
  std::vector<T> data;
  const F f;
  const T e;

 public:
  AbstractBinaryIndexedTree() = default;

  explicit AbstractBinaryIndexedTree(int n, const F f, const T& e)
      : n(n), f(f), e(e) {
    data.assign(n + 1, e);
  }

  explicit AbstractBinaryIndexedTree(const std::vector<T>& v, const F f,
                                     const T& e)
      : AbstractBinaryIndexedTree((int)v.size(), f, e) {
    build(v);
  }

  void build(const std::vector<T>& v) {
    assert(n == (int)v.size());
    for (int i = 1; i <= n; i++) data[i] = v[i - 1];
    for (int i = 1; i <= n; i++) {
      int j = i + (i & -i);
      if (j <= n) data[j] = f(data[j], data[i]);
    }
  }

  void apply(int k, const T& x) {
    for (++k; k <= n; k += k & -k) data[k] = f(data[k], x);
  }

  T prod(int r) const {
    T ret{e};
    for (; r > 0; r -= r & -r) ret = f(ret, data[r]);
    return ret;
  }
};

template <typename T, typename F>
AbstractBinaryIndexedTree<T, F> get_abstract_binary_indexed_tree(int n,
                                                                 const F& f,
                                                                 const T& e) {
  return AbstractBinaryIndexedTree{n, f, e};
}

template <typename T, typename F>
AbstractBinaryIndexedTree<T, F> get_abstract_binary_indexed_tree(
    const std::vector<T>& v, const F& f, const T& e) {
  return AbstractBinaryIndexedTree{v, f, e};
}
#line 2 "structure/others/binary-indexed-tree.hpp"

#line 5 "structure/others/binary-indexed-tree.hpp"

template <typename T>
struct BinaryIndexedTree {
 private:
  int n;
  std::vector<T> data;

 public:
  BinaryIndexedTree() = default;

  explicit BinaryIndexedTree(int n) : n(n) { data.assign(n + 1, T()); }

  explicit BinaryIndexedTree(const std::vector<T>& v)
      : BinaryIndexedTree((int)v.size()) {
    build(v);
  }

  void build(const std::vector<T>& v) {
    assert(n == (int)v.size());
    for (int i = 1; i <= n; i++) data[i] = v[i - 1];
    for (int i = 1; i <= n; i++) {
      int j = i + (i & -i);
      if (j <= n) data[j] += data[i];
    }
  }

  void apply(int k, const T& x) {
    for (++k; k <= n; k += k & -k) data[k] += x;
  }

  T prod(int r) const {
    T ret = T();
    for (; r > 0; r -= r & -r) ret += data[r];
    return ret;
  }

  T prod(int l, int r) const { return prod(r) - prod(l); }

  int lower_bound(T x) const {
    int i = 0;
    for (int k = 1 << (32 - __builtin_clz(n)); k > 0; k >>= 1) {
      if (i + k <= n && data[i + k] < x) {
        x -= data[i + k];
        i += k;
      }
    }
    return i;
  }

  int upper_bound(T x) const {
    int i = 0;
    for (int k = 1 << (32 - __builtin_clz(n)); k > 0; k >>= 1) {
      if (i + k <= n && data[i + k] <= x) {
        x -= data[i + k];
        i += k;
      }
    }
    return i;
  }
};
#line 10 "test/unittest/binary-indexed-trees.test.cpp"

int main() {
  {
    BinaryIndexedTree<int> tree(std::vector<int>{1, 2, 3, 4});
    assert(tree.prod(0) == 0);
    assert(tree.prod(4) == 10);
    assert(tree.prod(1, 3) == 5);
    assert(tree.lower_bound(1) == 0);
    assert(tree.lower_bound(4) == 2);
    assert(tree.lower_bound(11) == 4);
    assert(tree.upper_bound(0) == 0);
    assert(tree.upper_bound(3) == 2);
    assert(tree.upper_bound(10) == 4);
  }

  std::mt19937 rng(123456789);
  for (int n = 1; n <= 100; n++) {
    std::vector<int> values(n);
    BinaryIndexedTree<int> sum(n);
    for (int iteration = 0; iteration < 500; iteration++) {
      int index = rng() % n;
      int delta = rng() % 10;
      values[index] += delta;
      sum.apply(index, delta);

      int left = rng() % (n + 1);
      int right = rng() % (n + 1);
      if (left > right) std::swap(left, right);
      int expected = 0;
      for (int i = left; i < right; i++) expected += values[i];
      assert(sum.prod(left, right) == expected);
    }

    auto maximum = get_abstract_binary_indexed_tree(
        values, [](int a, int b) { return std::max(a, b); }, -1);
    int expected = -1;
    for (int right = 0; right <= n; right++) {
      if (right > 0) expected = std::max(expected, values[right - 1]);
      assert(maximum.prod(right) == expected);
    }
  }
}

Back to top page