#include #include #include #include #include #include #include template class DynamicSegTree { static_assert(std::is_convertible>::value, "type constraint merge :: T -> T -> T"); public: using index_t = int64_t; using value_t = T; private: struct Node; using node_ptr = std::unique_ptr; node_ptr body; const T _e; const Merge merge; const index_t lb, ub; struct Node { value_t val; const index_t _l; const index_t _r; node_ptr child[2]; Node(const value_t &x, const index_t l, const index_t r) : val(x), _l(l), _r(r), child{nullptr, nullptr} { } value_t get_value() const { return val; } index_t get_l() const { return _l; } index_t get_r() const { return _r; } void update(const index_t i, const value_t &x, const value_t e, const Merge merge) { if (get_l() + 1 == get_r()) { val = x; } else { index_t mid = (get_l() + get_r()) / 2; if (i < mid) { if (!child[0]) { child[0].reset(new Node(x, get_l(), mid)); } child[0]->update(i, x, e, merge); } else { if (!child[1]) { child[1].reset(new Node(x, mid, get_r())); } child[1]->update(i, x, e, merge); } val = merge(child[0] ? child[0]->get_value() : e, child[1] ? child[1]->get_value() : e); } } value_t query(index_t l, index_t r, const value_t e, const Merge merge) const { if (l <= get_l() && get_r() <= r) { return val; } else if (r < get_l() || get_r() < l) { return e; } else { return merge(child[0] ? child[0]->query(l, r, e, merge) : e, child[1] ? child[1]->query(l, r, e, merge) : e); } } std::string to_str(std::string prefix = "") const { std::string res; auto s = std::string("--") + std::to_string(val) + std::string("[") + std::to_string(_l) + std::string("~") + std::to_string(_r) + std::string("]"); res += s; int k = prefix.size(); k += 2; auto npre = prefix; for (unsigned int i = 0; i < s.size(); i++) npre += " "; if (child[1]) npre[k] = '|'; if (child[0]) { res += child[0]->to_str(npre); } else { res += "\n"; } if (child[1]) { npre[k] = '|'; res += npre; res += "\n"; res += prefix; res += " *"; for (unsigned int i = 0; i < s.size() - 3; i++) res += "-"; npre[k] = ' '; res += child[1]->to_str(npre); } return res; } }; public: DynamicSegTree(const value_t &e, const Merge merge_func, index_t lower, index_t upper) : body(new Node(e, lower, upper)), _e(e), merge(merge_func), lb(lower), ub(upper) { } void update(const index_t i, const value_t &x) { assert(lb <= i); assert(i < ub); if (body) { body->update(i, x, _e, merge); } } value_t query(index_t l, index_t r) { assert(lb <= l); assert(lb < r); assert(l < ub); assert(r <= ub); return body->query(l, r, _e, merge); } void deb() const { if (body) std::cout << body->to_str() << std::endl; } }; using namespace std; using ll = long long; int main() { ios::sync_with_stdio(false); std::cin.tie(nullptr); DynamicSegTree st(0LL, [](ll x, ll y) { return x + y; }, 0LL, 1LL << 30); int n; std::cin >> n; long long ans = 0; for (int i = 0; i < n; i++) { int id; std::cin >> id; if (id == 0) { int x, y; cin >> x >> y; st.update(x, st.query(x, x + 1) + y); } else { int l, r; std::cin >> l >> r; ans += st.query(l, r + 1); } } cout << ans << endl; }