#include using namespace std; #define rep(i, n) for (int i = 0; i < int(n); i++) #define per(i, n) for (int i = (n)-1; 0 <= i; i--) #define rep2(i, l, r) for (ll i = (l); i < ll(r); i++) #define per2(i, l, r) for (int i = (r)-1; int(l) <= i; i--) #define MM << " " << #define pb push_back #define eb emplace_back #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define sz(x) (int)x.size() template void print(const vector &v, T x = 0) { int n = v.size(); for (int i = 0; i < n; i++) cout << v[i] + x << (i == n - 1 ? '\n' : ' '); if (v.empty()) cout << '\n'; } template using MaxHeap = priority_queue; template using MinHeap = priority_queue, greater>; using ll = long long; using pii = pair; using pll = pair; template bool chmax(T &x, const T &y) { return (x < y) ? (x = y, true) : false; } template bool chmin(T &x, const T &y) { return (x > y) ? (x = y, true) : false; } #include #include #include template class DynamicSegTree { 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; struct Node { static constexpr index_t ub = (index_t)1 << (numeric_limits::digits - 1); static constexpr index_t lb = -ub; 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} { } std::pair next_lr() const { assert(_l < _r); auto intv = _r - _l; if ((_l | intv) == _r) { if (_l == 0 && _r == ub) { return {lb, ub}; } else { return {_l, _r + intv}; } } else { if (_l == lb && _r == 0) { return {lb, ub}; } else { return {_l - intv, _r}; } } } 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); } } void deb(string prefix = "") const { auto s = string("--") + to_string(val) + string("[") + to_string(_l) + string("-") + to_string(_r) + string("]"); cout << 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]) child[0]->deb(npre); else cout << "\n"; if (child[1]) { npre[k] = '|'; cout << npre << "\n"; cout << prefix << " *"; for (unsigned int i = 0; i < s.size() - 3; i++) cout << "-"; npre[k] = ' '; child[1]->deb(npre); } } }; void inflate() { auto [l, r] = body->next_lr(); node_ptr next_body = std::make_unique(body->get_value(), l, r); if (l == body->get_l()) { next_body->child[0] = move(body); } else { next_body->child[1] = move(body); } body = move(next_body); } public: DynamicSegTree(const value_t &e, const Merge merge_func) : body(nullptr), _e(e), merge(merge_func) { } void update(const index_t i, const value_t &x) { assert(Node::lb <= i); assert(i < Node::ub); if (body) { while (i < body->get_l() || body->get_r() <= i) { inflate(); } body->update(i, x, _e, merge); } else { body.reset(new Node(x, i, i + 1)); } } value_t query(index_t l, index_t r) { assert(Node::lb <= l); assert(Node::lb < r); assert(l < Node::ub); assert(r <= Node::ub); if (!body) { return _e; } return body->query(l, r, _e, merge); } void deb() const { body->deb(); cout << "\n\n"; } }; int main() { DynamicSegTree st(0, [](int x, int y) { return x + y; }); int n; std::cin >> n; int 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; }