class DynamicSegTree: def __init__(self, n, op, e): self.n = n self.op = op self.e = e # index 0 は番兵 (存在しない部分木 = 単位元) self.lc = [0] self.rc = [0] self.dat = [e] self.root = 0 def _new(self): self.lc.append(0) self.rc.append(0) self.dat.append(self.e) return len(self.dat) - 1 # ------------------------------------------------------------------ # 一点更新・取得 # ------------------------------------------------------------------ def set(self, p: int, x): """a[p] = x""" if p < 0 or p >= self.n: raise IndexError('DynamicSegTree: index out of range') if self.root == 0: self.root = self._new() t = self.root a = 0 b = self.n stack: list[int] = [] while b - a > 1: stack.append(t) m = a + ((b - a) >> 1) if p < m: nxt = self.lc[t] if nxt == 0: nxt = self._new() self.lc[t] = nxt t = nxt b = m else: nxt = self.rc[t] if nxt == 0: nxt = self._new() self.rc[t] = nxt t = nxt a = m self.dat[t] = x while len(stack) > 0: u = stack.pop() self.dat[u] = self.op(self.dat[self.lc[u]], self.dat[self.rc[u]]) def apply_at(self, p: int, x): """a[p] = op(a[p], x)。未作成の点は e 扱い。1 回の降下で処理。""" if p < 0 or p >= self.n: raise IndexError('DynamicSegTree: index out of range') if self.root == 0: self.root = self._new() t = self.root a = 0 b = self.n stack: list[int] = [] while b - a > 1: stack.append(t) m = a + ((b - a) >> 1) if p < m: nxt = self.lc[t] if nxt == 0: nxt = self._new() self.lc[t] = nxt t = nxt b = m else: nxt = self.rc[t] if nxt == 0: nxt = self._new() self.rc[t] = nxt t = nxt a = m self.dat[t] = self.op(self.dat[t], x) while len(stack) > 0: u = stack.pop() self.dat[u] = self.op(self.dat[self.lc[u]], self.dat[self.rc[u]]) def get(self, p: int): """a[p] を返す (未作成なら e)。""" if p < 0 or p >= self.n: raise IndexError('DynamicSegTree: index out of range') t = self.root a = 0 b = self.n while t != 0 and b - a > 1: m = a + ((b - a) >> 1) if p < m: t = self.lc[t] b = m else: t = self.rc[t] a = m return self.dat[t] # dat[0] == e なので未作成でも正しい def __getitem__(self, p: int): return self.get(p) def __setitem__(self, p: int, x): self.set(p, x) def build(self, v, offset: int = 0): """リスト v を区間 [offset, offset+len(v)) に一括代入。O(|v| log n)。""" for i in range(len(v)): self.set(offset + i, v[i]) # ------------------------------------------------------------------ # 区間積 (非可換モノイド対応・完全非再帰) # ------------------------------------------------------------------ def prod(self, l: int, r: int): """op(a[l], a[l+1], ..., a[r-1]) を返す。l >= r なら e。""" if l < 0: l = 0 if r > self.n: r = self.n if l >= r: return self.e # Phase 0: クエリが片側に収まる間は降下 t = self.root a = 0 b = self.n while t != 0: if l <= a and b <= r: return self.dat[t] m = a + ((b - a) >> 1) if r <= m: t = self.lc[t] b = m elif m <= l: t = self.rc[t] a = m else: break if t == 0: return self.e m = a + ((b - a) >> 1) # 左境界の降下: [l, m) を右から左へ畳み込む (resl = op(新区間, resl)) resl = self.e u = self.lc[t] x = a y = m while u != 0: if l <= x: resl = self.op(self.dat[u], resl) break mm = x + ((y - x) >> 1) if l < mm: rr = self.rc[u] if rr != 0: resl = self.op(self.dat[rr], resl) u = self.lc[u] y = mm else: u = self.rc[u] x = mm # 右境界の降下: [m, r) を左から右へ畳み込む (resr = op(resr, 新区間)) resr = self.e u = self.rc[t] x = m y = b while u != 0: if y <= r: resr = self.op(resr, self.dat[u]) break mm = x + ((y - x) >> 1) if r > mm: ll = self.lc[u] if ll != 0: resr = self.op(resr, self.dat[ll]) u = self.rc[u] x = mm else: u = self.lc[u] y = mm return self.op(resl, resr) def all_prod(self): return self.dat[self.root] # ------------------------------------------------------------------ # 木上二分探索 (ACL 互換。再帰だが深さは高々 log2(n) <= 63) # ------------------------------------------------------------------ def max_right(self, l: int, g): """g(op(a[l..r))) が true となる最大の r を返す。 条件: g(e) == true, 0 <= l <= n。g は単調 (true→…→false) を仮定。""" pos, _ = self._mr(self.root, 0, self.n, l, g, self.e) return self.n if pos < 0 else pos def _mr(self, t: int, a: int, b: int, l: int, g, sm): if b <= l or t == 0: return (-1, sm) # 空 or 全て e → sm 不変・境界なし if l <= a: tot = self.op(sm, self.dat[t]) if g(tot): return (-1, tot) # 区間全体 OK → 境界はさらに右 if b - a == 1: return (a, sm) # 境界確定 m = a + ((b - a) >> 1) pos, sm = self._mr(self.lc[t], a, m, l, g, sm) if pos >= 0: return (pos, sm) return self._mr(self.rc[t], m, b, l, g, sm) def min_left(self, r: int, g): """g(op(a[l..r))) が true となる最小の l を返す。 条件: g(e) == true, 0 <= r <= n。""" pos, _ = self._ml(self.root, 0, self.n, r, g, self.e) return 0 if pos < 0 else pos def _ml(self, t: int, a: int, b: int, r: int, g, sm): if a >= r or t == 0: return (-1, sm) if b <= r: tot = self.op(self.dat[t], sm) if g(tot): return (-1, tot) if b - a == 1: return (b, sm) m = a + ((b - a) >> 1) pos, sm = self._ml(self.rc[t], m, b, r, g, sm) if pos >= 0: return (pos, sm) return self._ml(self.lc[t], a, m, r, g, sm) # ------------------------------------------------------------------ # その他 # ------------------------------------------------------------------ def node_count(self) -> int: """生成済みノード数 (メモリ使用量の目安)。""" return len(self.dat) - 1 def clear(self): self.lc = [0] self.rc = [0] self.dat = [self.e] self.root = 0 N = int(input()) T = DynamicSegTree(10**9+100, int.__add__, 0) ans = 0 for _ in range(N): query = list(map(int,input().split())) if(query[0] == 0): _,x,y = query T.set(x, T.get(x) + y) else: _,l,r = query ans += T.prod(l,r+1) print(ans)