This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub kmyk/competitive-programming-library
#include "data_structure/binary_indexed_tree.hpp"
#pragma once
#include <cassert>
#include <vector>
#include "../utils/macros.hpp"
/**
* @brief Binary Indexed Tree
*/
template <typename CommutativeMonoid>
struct binary_indexed_tree {
typedef typename CommutativeMonoid::value_type value_type;
CommutativeMonoid mon;
std::vector<value_type> data;
binary_indexed_tree(int n, CommutativeMonoid const & mon_ = CommutativeMonoid())
: mon(mon_),
data(n, mon.unit()) {
}
template <class InputIterator>
binary_indexed_tree(InputIterator first, InputIterator last, CommutativeMonoid const & mon_ = CommutativeMonoid())
: mon(mon_),
data(first, last) {
REP3 (j, 1, data.size() + 1) {
int k = j + (j & -j);
if (k - 1 < static_cast<int>(data.size())) {
data[k - 1] = mon.mult(data[k - 1], data[j - 1]);
}
}
}
/**
* @note $a_i \gets a_i + z$
* @note $O(\log N)$
*/
void point_mult(int i, value_type z) {
assert (0 <= i and i < static_cast<int>(data.size()));
for (int j = i + 1; j <= static_cast<int>(data.size()); j += j & -j) {
data[j - 1] = mon.mult(data[j - 1], z);
}
}
/**
* @note $\sum _ {i \lt r} a_i$
* @note $O(\log N)$
*/
value_type initial_range_get(int r) {
assert (0 <= r and r <= static_cast<int>(data.size()));
value_type acc = mon.unit();
for (int i = r; 0 < i; i -= i & -i) {
acc = mon.mult(data[i - 1], acc);
}
return acc;
}
};
#line 2 "data_structure/binary_indexed_tree.hpp"
#include <cassert>
#include <vector>
#line 2 "utils/macros.hpp"
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
#line 5 "data_structure/binary_indexed_tree.hpp"
/**
* @brief Binary Indexed Tree
*/
template <typename CommutativeMonoid>
struct binary_indexed_tree {
typedef typename CommutativeMonoid::value_type value_type;
CommutativeMonoid mon;
std::vector<value_type> data;
binary_indexed_tree(int n, CommutativeMonoid const & mon_ = CommutativeMonoid())
: mon(mon_),
data(n, mon.unit()) {
}
template <class InputIterator>
binary_indexed_tree(InputIterator first, InputIterator last, CommutativeMonoid const & mon_ = CommutativeMonoid())
: mon(mon_),
data(first, last) {
REP3 (j, 1, data.size() + 1) {
int k = j + (j & -j);
if (k - 1 < static_cast<int>(data.size())) {
data[k - 1] = mon.mult(data[k - 1], data[j - 1]);
}
}
}
/**
* @note $a_i \gets a_i + z$
* @note $O(\log N)$
*/
void point_mult(int i, value_type z) {
assert (0 <= i and i < static_cast<int>(data.size()));
for (int j = i + 1; j <= static_cast<int>(data.size()); j += j & -j) {
data[j - 1] = mon.mult(data[j - 1], z);
}
}
/**
* @note $\sum _ {i \lt r} a_i$
* @note $O(\log N)$
*/
value_type initial_range_get(int r) {
assert (0 <= r and r <= static_cast<int>(data.size()));
value_type acc = mon.unit();
for (int i = r; 0 < i; i -= i & -i) {
acc = mon.mult(data[i - 1], acc);
}
return acc;
}
};