This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub tkmst201/Library
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_G" #include "DataStructure/BinaryIndexedTree_RangeAdd.hpp" #include <cstdio> int main() { int n, q; scanf("%d %d", &n, &q); using ll = long long; BinaryIndexedTree_RangeAdd<ll> bit(n); while (q--) { int query, s, t; scanf("%d %d %d", &query, &s, &t); --s; if (query == 0) { int x; scanf("%d", &x); bit.add(s, t, x); } else { printf("%lld\n", bit.sum(s, t)); } } }
#line 1 "Test/BinaryIndexedTree_RangeAdd.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_G" #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); } }; #line 4 "Test/BinaryIndexedTree_RangeAdd.test.cpp" #include <cstdio> int main() { int n, q; scanf("%d %d", &n, &q); using ll = long long; BinaryIndexedTree_RangeAdd<ll> bit(n); while (q--) { int query, s, t; scanf("%d %d %d", &query, &s, &t); --s; if (query == 0) { int x; scanf("%d", &x); bit.add(s, t, x); } else { printf("%lld\n", bit.sum(s, t)); } } }