output_description: For each getSum operation, print the sum in a line.
input_description: n q
      com1 x1 y1
      com2 x2 y2
      ...
      comq xq yq
      
  
  In the first line, n (the number of elements in A) and q (the number of
  queries) are given. Then, q queries are given where com represents the type of
  queries. '0' denotes add(xi, yi) and '1' denotes getSum(xi, yi).
attempt: import math
  import functools
  
  
  class SegmentTree:
      def __init__(self, a: list, default: int, op):
          real_size = len(a)
          self.elem_size = 1 << math.ceil(math.log2(real_size))
          self.tree_size = 2 * self.elem_size + 1
          self.tree = (
              [default] * (self.elem_size - 1)
              + a
              + [default] * (self.elem_size - real_size)
          )
          self.operation = op
  
      def get_range_index(self, x, y, k=0, l_end=0, r_end=None):
          if r_end is None:
              r_end = self.elem_size
  
          if l_end == x and y == r_end - 1:
              return [k]
          elif not l_end <= x <= y < r_end:
              return []
  
          mid = (l_end + r_end) // 2
          left_y = y if y < mid - 1 else mid - 1
          right_x = x if x > mid else mid
  
          left = self.get_range_index(x, left_y, 2 * k + 1, l_end, mid)
          right = self.get_range_index(right_x, y, 2 * k + 2, mid, r_end)
          return left + right
  
      def get_value(self, x, y):
          tree = self.tree
          index_list = self.get_range_index(x, y)
          op = self.operation
          return functools.reduce(op, (tree[n] for n in index_list))
  
      def update_tree(self, i: int):
          op = self.operation
  
          k = self.elem_size - 1 + 1
          tree = self.tree
          while k > 0:
              k = (k - 1) // 2
              left, right = tree[2 * k + 1], tree[2 * k + 2]
              tree[k] = op(left, right)
  
      def set_value(self, i: int, value: int, op: str):
          k = self.elem_size - 1 + i
          if op == "=":
              self.tree[k] = value
          elif op == "+":
              self.tree[k] += value
          self.update_tree(i)
  
  
  n, q = map(int, input().split())
  rsq = SegmentTree([0] * n, 0, lambda x, y: x + y)
  ans = []
  for _ in [0] * q:
      c, x, y = map(int, input().split())
      if c == 0:
          rsq.set_value(x - 1, y - 1, "+")
      else:
          ans.append(rsq.get_value(x, y))
  print("\n".join([str(n) for n in ans]))
  
problem_description: Range Sum Query
  
  Write a program which manipulates a sequence A = {a1, a2, . . . , an} with the
  following operations:
  
    * add(i, x): add x to ai.
    * getSum(s, t): print the sum of as, as+1,...,at.
  
  Note that the initial values of ai (i = 1, 2, . . . , n) are 0.
samples: [{"input": "3 5\n    0 1 1\n    0 2 2\n    0 3 3\n    1 1 2\n    1 2 2", "output": "3\n    2"}]