This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_G" #include <iostream> #include "C++/ds/fwtree/RangeBIT.hpp" int main() { int n, q; std::cin >> n >> q; RangeBIT<int64_t> bit(n); while(q--) { int h, s, t; std::cin >> h >> s >> t; s--; if(h == 0) { int x; std::cin >> x; bit.add(s, t, x); } else { std::cout << bit.sum(s, t) << '\n'; } } }
#line 1 "test/fwtree3.test.cpp" #define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_G" #include <iostream> #line 2 "C++/ds/fwtree/RangeBIT.hpp" #line 2 "C++/ds/fwtree/FenwickTree.hpp" #include <vector> template <class T> struct FenwickTree { private: int n; std::vector<T> data; void init(const size_t size) { n = size + 2; data.resize(n + 1); } public: FenwickTree(){} FenwickTree(const size_t size){ init(size); } FenwickTree(const std::vector<T> &a) { init(a.size()); for(size_t i = 0; i < a.size(); ++i) { add(i, a[i]); } } T sum(int k) const { if(k < 0) { return 0; } T ret = 0; for(++k; k > 0; k -= k & -k) { ret += data[k]; } return ret; } inline T sum(int l, int r) const { return sum(r) - sum(l - 1); } inline T operator[](int k) const { return sum(k) - sum(k - 1); } void add(int k, const T &x) { for(++k; k < n; k += k & -k) { data[k] += x; } } void add(const int l, const int r, const T& x) { add(l, x); add(r + 1, -x); } int lower_bound(T w) { if(w <= 0) { return 0; } int x = 0; for(int k = 1 << std::__lg(n); k; k >>= 1) { if(x + k <= n - 1 && data[x + k] < w) { w -= data[x + k]; x += k; } } return x; } int upper_bound(T w) { if(w < 0) { return 0; } int x = 0; for(int k = 1 << std::__lg(n); k; k >>= 1) { if(x + k <= n - 1 && data[x + k] <= w) { w -= data[x + k]; x += k; } } return x; } }; /** * @brief Binary Indexed Tree * @see https://nyaannyaan.github.io/library/data-structure/binary-indexed-tree.hpp */ #line 4 "C++/ds/fwtree/RangeBIT.hpp" template <class T> struct RangeBIT { private: FenwickTree<T> a, b; public: RangeBIT(const int n): a(n + 1), b(n + 1){} RangeBIT(const std::vector<T> &v) { this(v.size()); for(size_t i = 0; i < v.size(); ++i) { add(i, i + 1, v[i]); } } void add(const int l, const int r, const T &x) { a.add(l, x); a.add(r, -x); b.add(l, x * (1 - l)); b.add(r, x * (r - 1)); } inline T operator[](const int i) const { return sum(i, i + 1); } inline T sum(int l, int r) { l--, r--; return a.sum(r) * r + b.sum(r) - a.sum(l) * l - b.sum(l); } }; /** * @brief Range BIT */ #line 4 "test/fwtree3.test.cpp" int main() { int n, q; std::cin >> n >> q; RangeBIT<int64_t> bit(n); while(q--) { int h, s, t; std::cin >> h >> s >> t; s--; if(h == 0) { int x; std::cin >> x; bit.add(s, t, x); } else { std::cout << bit.sum(s, t) << '\n'; } } }