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_B" #include "DataStructure/BinaryIndexedTree.hpp" #include <cstdio> int main() { int n, q; scanf("%d %d", &n, &q); BinaryIndexedTree<int> bit(n, 0, [](auto &&x, auto &&y) { return x + y; }); while (q--) { int com, x, y; scanf("%d %d %d", &com, &x, &y); if (com == 0) bit.add(x - 1, y); else printf("%d\n", bit.sum(y) - bit.sum(x - 1)); } }
#line 1 "Test/BinaryIndexedTree.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B" #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 4 "Test/BinaryIndexedTree.test.cpp" #include <cstdio> int main() { int n, q; scanf("%d %d", &n, &q); BinaryIndexedTree<int> bit(n, 0, [](auto &&x, auto &&y) { return x + y; }); while (q--) { int com, x, y; scanf("%d %d %d", &com, &x, &y); if (com == 0) bit.add(x - 1, y); else printf("%d\n", bit.sum(y) - bit.sum(x - 1)); } }