This documentation is automatically generated by online-judge-tools/verification-helper
#include "DataStructure/BinaryIndexedTree_RangeAdd.hpp"
Binary Indexed Tree を用いた配列の区間和を扱うデータ構造です。
要素数 $N$ の配列に対し、区間一樣加算や任意の区間和の計算を $\Theta(\log{N})$ で行うことができます。
遅延セグメント木 に比べ、より省メモリで定数倍が良いです。
BinaryIndexedTree(size_t n)
size_t size()
void add(size_t l, size_t r, T x)
T sum(size_t i)
T sum(size_t l, size_t r)
制約
T
は int
, long long
, ModInt
要素数 $n$ で初期化します。 初期値は $0$ です。
計算量
以下、要素数 $N$ の配列 $A_0, A_1, \ldots, A_{N-1}$ を対象とします。
配列の要素数 $N$ を返します。
計算量
$i = l, l+1, \ldots, r-1$ に対して $A_i$ += $x$ をします。 $l = r$ のときは何も行いません。
制約
計算量
$\sum_{k=0}^{i-1} A_k$ を返します。 $i = 0$ のときは $0$ を返します。
制約
計算量
$\sum_{k=l}^{r-1} A_k$ を返します。 $l = r$ のときは $0$ を返します。
制約
計算量
オーバーフローに注意してください。総和が $2^{31}$ 以上になる場合は long long
を使いましょう。
#include <bits/stdc++.h>
#include "DataStructure/BinaryIndexedTree_RangeAdd.hpp"
using namespace std;
int main() {
BinaryIndexedTree_RangeAdd<int> bit(5);
cout << "N = " << bit.size() << endl; // 5
bit.add(1, 3, 2);
// 0 2 2 0 0
for (int i = 0; i < bit.size(); ++i) cout << bit.sum(i, i + 1) << " \n"[i + 1 == bit.size()];
bit.add(0, 2, -1);
// -1 1 2 0 0
for (int i = 0; i < bit.size(); ++i) cout << bit.sum(i, i + 1) << " \n"[i + 1 == bit.size()];
cout << "sum = " << bit.sum(bit.size()) << endl; // 2
}
2020/08/15: https://algo-logic.info/binary-indexed-tree/
#ifndef INCLUDE_GUARD_BINARY_INDEXED_TREE_RANGE_ADD_HPP
#define INCLUDE_GUARD_BINARY_INDEXED_TREE_RANGE_ADD_HPP
#include "DataStructure/BinaryIndexedTree.hpp"
#include <vector>
#include <cassert>
/**
* @brief https://tkmst201.github.io/Library/DataStructure/BinaryIndexedTree_RangeAdd.hpp
*/
template<typename T>
struct BinaryIndexedTree_RangeAdd {
static_assert(std::is_integral<T>::value == true);
using bit_type = BinaryIndexedTree<T>;
using value_type = typename bit_type::value_type;
using size_type = typename bit_type::size_type;
private:
std::vector<bit_type> bit;
public:
explicit BinaryIndexedTree_RangeAdd(size_type n)
: bit(2, bit_type{n, 0, [](value_type x, value_type y) { return x + y; }}) {}
size_type size() const noexcept {
return bit[0].size();
}
void add(size_type l, size_type r, value_type x) noexcept {
assert(l <= r);
assert(r <= size());
if (l == r) return;
bit[0].add(l, x);
bit[0].add(r - 1, -x);
bit[1].add(l, -x * l);
bit[1].add(r - 1, x * r);
}
value_type sum(size_type i) noexcept {
assert(i <= size());
return bit[0].sum(i) * i + bit[1].sum(i);
}
value_type sum(size_type l, size_type r) noexcept {
assert(l <= r);
assert(r <= size());
if (l == r) return 0;
return sum(r) - sum(l);
}
};
#endif // INCLUDE_GUARD_BINARY_INDEXED_TREE_RANGE_ADD_HPP
#line 1 "DataStructure/BinaryIndexedTree_RangeAdd.hpp"
#line 1 "DataStructure/BinaryIndexedTree.hpp"
#include <vector>
#include <cassert>
#include <functional>
/**
* @brief https://tkmst201.github.io/Library/DataStructure/BinaryIndexedTree.hpp
*/
template<typename T>
struct BinaryIndexedTree {
using value_type = T;
using const_reference = const value_type &;
using F = std::function<value_type (const_reference, const_reference)>;
using size_type = std::size_t;
private:
size_type n;
value_type id_elem;
F f;
std::vector<value_type> node;
public:
BinaryIndexedTree(size_type n, const_reference id_elem, const F & f)
: n(n), id_elem(id_elem), f(f), node(n + 1, id_elem) {}
size_type size() const noexcept {
return n;
}
void add(size_type i, const_reference x) noexcept {
assert(i < size());
++i;
for (; i <= size(); i += i & -i) node[i] = f(node[i], x);
}
value_type sum(size_type i) const noexcept {
assert(i <= size());
value_type res = id_elem;
for (; i > 0; i -= i & -i) res = f(node[i], res);
return res;
}
size_type lower_bound(const_reference x) const noexcept {
size_type res = 0;
size_type s = id_elem, w = 1;
while (w < size()) w <<= 1;
for (; w > 0; w >>= 1) {
if (res + w <= size()) {
value_type cur = f(s, node[res + w]);
if (cur < x) {
res += w;
s = cur;
}
}
}
return res;
}
};
#line 5 "DataStructure/BinaryIndexedTree_RangeAdd.hpp"
#line 8 "DataStructure/BinaryIndexedTree_RangeAdd.hpp"
/**
* @brief https://tkmst201.github.io/Library/DataStructure/BinaryIndexedTree_RangeAdd.hpp
*/
template<typename T>
struct BinaryIndexedTree_RangeAdd {
static_assert(std::is_integral<T>::value == true);
using bit_type = BinaryIndexedTree<T>;
using value_type = typename bit_type::value_type;
using size_type = typename bit_type::size_type;
private:
std::vector<bit_type> bit;
public:
explicit BinaryIndexedTree_RangeAdd(size_type n)
: bit(2, bit_type{n, 0, [](value_type x, value_type y) { return x + y; }}) {}
size_type size() const noexcept {
return bit[0].size();
}
void add(size_type l, size_type r, value_type x) noexcept {
assert(l <= r);
assert(r <= size());
if (l == r) return;
bit[0].add(l, x);
bit[0].add(r - 1, -x);
bit[1].add(l, -x * l);
bit[1].add(r - 1, x * r);
}
value_type sum(size_type i) noexcept {
assert(i <= size());
return bit[0].sum(i) * i + bit[1].sum(i);
}
value_type sum(size_type l, size_type r) noexcept {
assert(l <= r);
assert(r <= size());
if (l == r) return 0;
return sum(r) - sum(l);
}
};