#line 2 "main.cpp" #include #line 5 "main.cpp" namespace kyopro { /// @brief 動的セグメント木 template class dynamic_segtree { public: dynamic_segtree(size_t n) : n(n), root(nullptr) {} private: struct Node { S val; std::shared_ptr l, r; std::shared_ptr parent; Node(const S& v, std::shared_ptr parent) : val(v), l(nullptr), r(nullptr), parent(parent) {} }; using sptr = std::shared_ptr; sptr root = nullptr; size_t n; S fold(const sptr& p) const { return p ? p->val : e(); } public: void update(size_t i, const S& v) { if (!root) { root = std::make_shared(e(), nullptr); } size_t ng = 0, ok = n; sptr ptr = root; while (ok - ng > 1) { size_t md = (ng + ok) >> 1; if (i < md) { if (!(ptr->l)) { ptr->l = std::make_shared(e(), ptr); } ptr = ptr->l; ok = md; } else { if (!(ptr->r)) { ptr->r = std::make_shared(e(), ptr); } ptr = ptr->r; ng = md; } } ptr->val = v; while (ptr->parent) { ptr->parent->val = op(fold(ptr->parent->l), fold(ptr->parent->r)); ptr = ptr->parent; } } S prod(size_t l, size_t r) { assert(0 <= l && l <= r && r <= n); if (l == r) { return e(); } return internal_prod(root, 0, n, l, r); } private: S internal_prod(sptr& p, size_t l, size_t r, size_t L, size_t R) { if (!p || r <= L || R <= l) { return e(); } if (L <= l && r <= R) { return p->val; } size_t mid = (l + r) >> 1; return op(internal_prod(p->l, l, mid, L, R), internal_prod(p->r, mid, r, L, R)); } }; }; // namespace kyopro /// @docs docs/data-structure/dynamic_segtree.md #line 82 "main.cpp" inline int op(int x, int y) { return x + y; } inline int e() { return 0; } int main() { const size_t n = 1000000001; kyopro::dynamic_segtree seg(n); int q; std::cin >> q; long long ans = 0; while (q--) { int type; std::cin >> type; if (type == 0) { size_t x; long long y; std::cin >> x >> y; seg.update(x, seg.prod(x, x + 1) + y); } else { size_t l, r; std::cin >> l >> r; ans += seg.prod(l, r + 1); } } std::cout << ans << '\n'; }