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, sys
  
  
  # ??°????????????????????§????¨????????????¨???????????°??????????????????????§????
  class SegmentTree:
      def __init__(self, n):
          self.TreeRange = pow(2, math.ceil(math.log2(n)))
          self.List = [0] * (2 * self.TreeRange - 1)
  
      def add(self, i, x):
          i += self.TreeRange - 1
          self.List[i] += x
          while i > 0:
              i = (i - 1) // 2
              self.List[i] += x
  
      def getsum(self, s, t, i=0, left=0, right=float("inf")):
          # ??¢?´¢????±?????????????????????§????????°0????????????
          if right <= s or t <= left:
              return 0
          # ??¢?´¢????±?????????????????????§????????°??????????????????????????????
          elif s <= left <= right <= t:
              return self.List[i]
          # ??¢?´¢????±????????????????????????????????????°????????????????????°
          else:
              l = self.getsum(s, t, i * 2 + 1, left, (left + right) // 2)
              r = self.getsum(s, t, i * 2 + 2, (left + right) // 2, right)
              return l + r
  
  
  _input = sys.stdin.readlines()
  n, q = map(int, _input[0].split())
  qlist = map(lambda x: x.split(), _input[1:])
  ST = SegmentTree(n)
  
  for q in qlist:
      cmd, x, y = map(int, q)
      if cmd == 0:
          ST.add(x, y)
      elif cmd == 1:
          print(ST.getsum(x, y + 1, right=ST.TreeRange))
  
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"}]