C++ Library for Competitive Programming
/*
* @title データ構造/Fenwick tree/区間加算クエリ対応 Fenwick tree
*
* verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_G
*/
#include <iostream>
#include "emthrm/data_structure/fenwick_tree/fenwick_tree_supporting_range_add_query.hpp"
int main() {
int n, q;
std::cin >> n >> q;
emthrm::FenwickTreeSupportingRangeAddQuery<long long> bit(n);
while (q--) {
int kind, s, t;
std::cin >> kind >> s >> t;
--s; --t;
if (kind == 0) {
int x;
std::cin >> x;
bit.add(s, t + 1, x);
} else if (kind == 1) {
std::cout << bit.sum(s, t + 1) << '\n';
}
}
return 0;
}
#line 1 "test/data_structure/fenwick_tree/fenwick_tree_supporting_range_add_query.test.cpp"
/*
* @title データ構造/Fenwick tree/区間加算クエリ対応 Fenwick tree
*
* verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_G
*/
#include <iostream>
#line 1 "include/emthrm/data_structure/fenwick_tree/fenwick_tree_supporting_range_add_query.hpp"
#include <vector>
namespace emthrm {
template <typename Abelian>
struct FenwickTreeSupportingRangeAddQuery {
explicit FenwickTreeSupportingRangeAddQuery(
const int n_, const Abelian ID = 0)
: n(n_ + 1), ID(ID) {
data_const.assign(n, ID);
data_linear.assign(n, ID);
}
void add(int left, const int right, const Abelian val) {
if (right < ++left) [[unlikely]] return;
for (int i = left; i < n; i += i & -i) {
data_const[i] -= val * (left - 1);
data_linear[i] += val;
}
for (int i = right + 1; i < n; i += i & -i) {
data_const[i] += val * right;
data_linear[i] -= val;
}
}
Abelian sum(const int idx) const {
Abelian res = ID;
for (int i = idx; i > 0; i -= i & -i) {
res += data_linear[i];
}
res *= idx;
for (int i = idx; i > 0; i -= i & -i) {
res += data_const[i];
}
return res;
}
Abelian sum(const int left, const int right) const {
return left < right ? sum(right) - sum(left) : ID;
}
Abelian operator[](const int idx) const { return sum(idx, idx + 1); }
private:
const int n;
const Abelian ID;
std::vector<Abelian> data_const, data_linear;
};
} // namespace emthrm
#line 10 "test/data_structure/fenwick_tree/fenwick_tree_supporting_range_add_query.test.cpp"
int main() {
int n, q;
std::cin >> n >> q;
emthrm::FenwickTreeSupportingRangeAddQuery<long long> bit(n);
while (q--) {
int kind, s, t;
std::cin >> kind >> s >> t;
--s; --t;
if (kind == 0) {
int x;
std::cin >> x;
bit.add(s, t + 1, x);
} else if (kind == 1) {
std::cout << bit.sum(s, t + 1) << '\n';
}
}
return 0;
}