Problem:
Range Sum Query Write a program which manipulates a sequence A = { a 1 , a 2 , . . . , a n } with the following operations:  add(i, x) : add x to a i .  getSum(s, t) : print the sum of a s , a s+1 ,...,a t .  Note that the initial values of a i ( i = 1, 2, . . . , n ) are 0. Input  n  q  com 1  x 1  y 1  com 2  x 2  y 2 ... com q  x q  y q  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(x i , y i ) and '1' denotes getSum(x i , y i ) . Output For each getSum operation, print the sum in a line. Constraints   1 ≤ n ≤ 100000    1 ≤ q ≤ 100000   If com i is 0, then 1 ≤ x i ≤ n , 0 ≤ y i ≤ 1000 .  If com i is 1, then 1 ≤ x i ≤ n , 1 ≤ y i ≤ n .  Sample Input 1 3 5
0 1 1
0 2 2
0 3 3
1 1 2
1 2 2 Sample Output 1 3
2

Solution (Python):

class SegmentTree:
    def __init__(self, n):
        size = 1
        while size < n:
            size *= 2
        self.size = 2*size - 1
        self.data = [0] * self.size

    def add(self, i, v):
        
        index = self.size // 2 + i
        self.data[index] += v
        while index > 0:
            index = (index-1) // 2
            self.data[index] = self.data[index*2 + 1] + self.data[index*2 + 2]

    def sum(self, lo, hi):
        def _sum(r, i, j):
            if j < lo or i > hi:
                return 0
            elif lo <= i and j <= hi:
                return self.data[r]
            else:
                mid = i + (j - i)//2
                return _sum(r*2 + 1, i, mid) + _sum(r*2 + 2, mid+1, j)

        
        
        

        return _sum(0, 0, self.size//2)


def run():
    n, q = [int(i) for i in input().split()]

    t = SegmentTree(n)
    for _ in range(q):
        com, x, y = [int(i) for i in input().split()]
        if com == 0:
            t.add(x-1, y)
        else:
            print(t.sum(x-1, y-1))


if __name__ == '__main__':
    run()

Solution (Python):
n, q = map(int, input().split())

answer = []

size = 1

while size < n :
    size *= 2
    
size = size * 2 - 1

segtree = [0 for x in range(size)]




def update(i, x) :
    ind = size // 2 + i
    segtree[ind] += x
    
    while ind :
        ind = (ind - 1) // 2 
        ch1 = segtree[ind * 2 + 1]
        ch2 = segtree[ind * 2 + 2]
        segtree[ind] = ch1 + ch2
    
def query(s, t, l, r, p) :
    if s > r or t < l :
        return 0
    if s <= l and t >= r :
        return segtree[p]
    else :
        vl = query(s, t, l, (l + r) // 2, p * 2 + 1)
        vr = query(s, t, (l + r) // 2 + 1, r, p * 2 + 2)
        
        return vl + vr
    
for i in range(q) :
    
    com, x, y = map(int, input().split())
     
    if com == 0 :
        update(x - 1, y)
    else :
        answer.append(query(x - 1, y - 1, 0, size // 2, 0))

for a in answer :
    print(a)

Solution (Python):
n, q = map(int, input().split())


DEF = 0


seg_size = 2

while seg_size < n :
    seg_size *= 2
    
seg_size = seg_size * 2 - 1
seg_tree = [DEF for x in range(seg_size)]

answer_stk = []


def update(i, x) :
    
    idx = seg_size // 2 + i
    seg_tree[idx] += x
    
    while idx :
        idx = (idx - 1) // 2
        l_child = seg_tree[idx * 2 + 1]
        r_child = seg_tree[idx * 2 + 2]
        
        seg_tree[idx] = l_child + r_child


def query(s, t, l, r, curnode) :
    
    if s > r or t < l :
        return DEF
    
    
    if s <= l and t >= r :
        return seg_tree[curnode]
    
    
    else :
        l_child = curnode * 2 + 1
        r_child = curnode * 2 + 2
        
        l_value = query(s, t, l, (l + r) // 2, l_child)
        r_value = query(s, t, (l + r) // 2 + 1, r, r_child)
        
        return l_value + r_value
    

for i in range(q) :
    q, x, y = map(int, input().split())
    
    
    if q == 0 :
        update(x - 1, y)
        
    
    else :
        answer_stk.append(query(x - 1, y - 1, 0, seg_size // 2, 0))
        
for a in answer_stk :
    print(a)

Solution (Python):
import sys


class BIT:
    def __init__(self, node_size):
        self._node = node_size+1
        self.bit = [0]*self._node

    def add(self, index, add_val):
        index += 1
        while index < self._node:
            self.bit[index] += add_val
            index += index & -index

    def sum(self, index):
        index += 1
        res = 0
        while index > 0:
            res += self.bit[index]
            index -= index & -index
        return res

if __name__ == '__main__':
    n, q = map(int, sys.stdin.readline().split())
    bt = BIT(n)
    for i in range(q):
        a, b, c = map(int, sys.stdin.readline().split())
        if a == 0:
            bt.add(b-1, c)
        else:
            print(bt.sum(c-1)-bt.sum(b-2))

Solution (Python):
import sys


class BIT:
    def __init__(self, node_size):
        self._node = node_size+1
        self.bit = [0]*self._node

    def add(self, index, add_val):
        while index < self._node:
            self.bit[index] += add_val
            index += index & -index

    def sum(self, index):
        res = 0
        while index > 0:
            res += self.bit[index]
            index -= index & -index
        return res

if __name__ == '__main__':
    n, q = map(int, sys.stdin.readline().split())
    bt = BIT(n)
    for i in range(q):
        a, b, c = map(int, sys.stdin.readline().split())
        if a == 0:
            bt.add(b, c)
        else:
            print(bt.sum(c)-bt.sum(b-1))

Solution (Python):
import sys


class BIT:
    def __init__(self, node_size):
        self._node = node_size+1
        self.bit = [0]*self._node

    def add(self, index, add_val):
        while index < self._node:
            self.bit[index] += add_val
            index += index & -index

    def sum(self, index):
        res = 0
        while index > 0:
            res += self.bit[index]
            index -= index & -index
        return res

if __name__ == '__main__':
    n, q = map(int, sys.stdin.readline().split())
    bt = BIT(n)
    for i in range(q):
        a, b, c = map(int, sys.stdin.readline().split())
        if a == 0:
            bt.add(b, c)
        else:
            print(bt.sum(c)-bt.sum(b-1))

Solution (Python):
dat = [0] * 400000
m = 0

def init():
    global dat, m
    for i in range(2 * m - 1):
        dat[i] = 0

def add(i, x):
    global dat, m
    i += m - 1
    dat[i] += x
    while i > 0:
        i = (i - 1) // 2
        dat[i] = dat[2 * i + 1] + dat[2 * i + 2]

def getSum(a, b, k, l, r):
    global dat, m
    if r <= a or b <= l:
        return 0
    if a <= l and r <= b:
        return dat[k]
    else:
        vl = getSum(a, b, 2 * k + 1, l, (l + r) // 2)
        vr = getSum(a, b, 2 * k + 2, (l + r) // 2, r)
        return vl + vr

n, q = map(int, input().split())
m = 1
while m < n:
    m *= 2

for _ in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        add(x - 1, y)
    else:
        print(getSum(x - 1, y, 0, 0, m))

Solution (Python):
import sys


class BinaryIndexedTree(object):
    __slots__ = ["tree"]

    def __init__(self, size: int):
        self.tree = [0]*(size+1)

    def add(self, index: int, value: int) -> None:
        tree = self.tree
        next_index = index + 1

        while next_index < len(tree):
            tree[next_index] += value
            next_index += next_index & -next_index

    def sum(self, index: int):
        tree, result = self.tree, 0
        next_index = index + 1

        while next_index:
            result += tree[next_index]
            next_index -= next_index & -next_index

        return result


if __name__ == "__main__":
    n, q = map(int, input().split())
    bit = BinaryIndexedTree(n)
    result = []
    for com, x, y in (map(int, l.split()) for l in sys.stdin):
        if not com:
            bit.add(x-1, y)
        else:
            result.append(bit.sum(y-1) - bit.sum(x-2))

    print(*result, sep="\n")

Solution (Python):
class TemplateTree:
  def __init__(self, iterable):
    self.iter_size = self.get_size(iterable)
    self.size = self.iter_size * 2 - 1
    self.value = [None] * self.size
    for i, v in enumerate(iterable):
      self.value[self.iter_size + i - 1] = v
    self.set_value(0)
    self.range = [None] * self.size
    self.set_range(0, 0, self.iter_size - 1)
  
  def get_size(self, iterable):
    ret = 1
    x = len(iterable)
    while ret < x:
      ret *= 2
    return ret
  
  def set_range(self, x, left, right):
    self.range[x] = (left, right)
    if left != right:
      self.set_range(x * 2 + 1, left, (right + left) // 2)
      self.set_range(x * 2 + 2, (right + left) // 2 + 1, right)

  def set_value(self, x):
    if x >= self.iter_size - 1:return self.value[x]
    a = self.set_value(x * 2 + 1)
    b = self.set_value(x * 2 + 2)
    if a == None and b == None:
      self.value[x] = None
    elif a == None:
      self.value[x] = b
    elif b == None:
      self.value[x] = a
    else:
      self.value[x] = a + b
    return self.value[x]

  def update(self, i, x):
    target = self.iter_size + i - 1
    while target >= 0:
      self.value[target] += x
      target = (target - 1) // 2

  def query(self, x, left, right):
    x_left, x_right = self.range[x]
    if right < x_left or x_right < left:
      
      return 0
    if x_left < left and right < x_right:
      
      return self.query(x * 2 + 1, left, right) + self.query(x * 2 + 2, left, right)
    if x_left < left and x_right <= right:
      
      return self.query(x * 2 + 1, left, right) + self.query(x * 2 + 2, left, right)
    if left <= x_left and right < x_right:
      
      return self.query(x * 2 + 1, left, right) + self.query(x * 2 + 2, left, right)
    if left <= x_left and x_right <= right:
      
      return self.value[x]

  def print_tree(self):
    print(self.value)
    print(self.range)

n, q = map(int, input().split())
tree = TemplateTree([0] * n)

for _ in range(q):
  c, x, y = map(int, input().split())
  if c == 0:
    tree.update(x - 1, y)
  else:
    print(tree.query(0, x - 1, y - 1))

Solution (Python):
class TemplateTree:
  def __init__(self, iterable):
    self.iter_size = self.get_size(iterable)
    self.size = self.iter_size * 2 - 1
    self.value = [None] * self.size
    for i, v in enumerate(iterable):
      self.value[self.iter_size + i - 1] = v
    self.set_value(0)
    self.range = [None] * self.size
    self.set_range(0, 0, self.iter_size - 1)
  
  def get_size(self, iterable):
    ret = 1
    x = len(iterable)
    while ret < x:
      ret *= 2
    return ret
  
  def set_range(self, x, left, right):
    self.range[x] = (left, right)
    if left != right:
      self.set_range(x * 2 + 1, left, (right + left) // 2)
      self.set_range(x * 2 + 2, (right + left) // 2 + 1, right)

  def set_value(self, x):
    if x >= self.iter_size - 1:return self.value[x]
    a = self.set_value(x * 2 + 1)
    b = self.set_value(x * 2 + 2)
    if a == None and b == None:
      self.value[x] = None
    elif a == None:
      self.value[x] = b
    elif b == None:
      self.value[x] = a
    else:
      self.value[x] = a + b
    return self.value[x]

  def update(self, i, x):
    target = self.iter_size + i - 1
    while target >= 0:
      self.value[target] += x
      target = (target - 1) // 2

  def query(self, x, left, right):
    x_left, x_right = self.range[x]
    if right < x_left or x_right < left:
      return 0
    if left <= x_left and x_right <= right:
      return self.value[x]

    return self.query(x * 2 + 1, left, right) + self.query(x * 2 + 2, left, right)

  def print_tree(self):
    print(self.value)
    print(self.range)

n, q = map(int, input().split())
tree = TemplateTree([0] * n)

for _ in range(q):
  c, x, y = map(int, input().split())
  if c == 0:
    tree.update(x - 1, y)
  else:
    print(tree.query(0, x - 1, y - 1))

Solution (Python):
import sys

def initialize(N):
    i = 1
    while i < N:
        i *= 2
    return [0] * (2 * i - 1), i

def add(i, x, L, d):
    K = i + d - 1
    L[K] += x
    while K > 0:
        K = (K-1)//2
        L[K] += x

def getSum(s, t, index, l, r, L): 
    if r <= s or t <= l: return 0
    elif s <= l and r <= t: return L[index]
    else:
        sumL = getSum(s, t, 2 * index + 1, l, (l+r)//2, L)
        sumR = getSum(s, t, 2 * index + 2, (l+r)//2, r, L)
        return sumL + sumR

F = sys.stdin
N, Q = map(int, F.readline().strip("\n").split(" "))
SegTree, d = initialize(N)
for _ in range(Q):
    com, x, y = map(int, F.readline().strip("\n").split(" "))
    if com == 0: add(x-1, y, SegTree, d)
    elif com == 1:
        print(getSum(x-1, y, 0, 0, d, SegTree))

Solution (Python):


import sys

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')

class BIT:
    
    def __init__(self, n):
        
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    
    def sum(self, i):
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    
    def get(self, l, r=None):
        
        if r is None: r = l+1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

N,Q=MAP()
bit=BIT(N+1)
for _ in range(Q):
    com,x,y=MAP()
    if com==0:
        bit.add(x, y)
    else:
        print(bit.get(x, y+1))

Solution (Python):
import operator


class SegmentTree:
    
    def __init__(self, size, fn=operator.add, default=0):
        """
        :param int size:
        :param callable fn: 区間に適用する関数。引数を 2 つ取る。min, max, operator.xor など
        """
        
        n = 1
        while n < size:
            n *= 2
        self._size = n
        self._tree = [default for _ in range(self._size * 2 - 1)]
        self._fn = fn

    def set(self, i, value):
        """
        i 番目に value を設定
        :param int i:
        :param int value:
        :return:
        """
        x = self._size - 1 + i
        self._tree[x] = value

        while x > 0:
            x = (x - 1) // 2
            self._tree[x] = self._fn(self._tree[x * 2 + 1], self._tree[x * 2 + 2])

    def add(self, i, value):
        """
        もとの i 番目と value に fn を適用したものを i 番目に設定
        :param int i:
        :param int value:
        :return:
        """
        x = self._size - 1 + i
        self.set(i, self._fn(self._tree[x], value))

    def get(self, from_i, to_i, k=0, L=None, r=None):
        """
        [from_i, to_i) に fn を適用した結果を返す
        :param int from_i:
        :param int to_i:
        :param int k: self._tree[k] が、[L, r) に fn を適用した結果を持つ
        :param int L:
        :param int r:
        :return:
        """
        L = 0 if L is None else L
        r = self._size if r is None else r

        if from_i <= L and r <= to_i:
            return self._tree[k]

        if to_i <= L or r <= from_i:
            return None

        ret_L = self.get(from_i, to_i, k * 2 + 1, L, (L + r) // 2)
        ret_r = self.get(from_i, to_i, k * 2 + 2, (L + r) // 2, r)
        if ret_L is None:
            return ret_r
        if ret_r is None:
            return ret_L
        return self._fn(ret_L, ret_r)

    def __len__(self):
        return self._size


N, Q = list(map(int, input().split()))
com, X, Y = zip(*[input().split() for _ in range(Q)])
X = list(map(int, X))
Y = list(map(int, Y))

if __name__ == '__main__':
    st = SegmentTree(size=N + 1, fn=operator.add, default=0)
    for c, x, y in zip(com, X, Y):
        if c == '0':
            st.add(x, y)
        if c == '1':
            print(st.get(x, y + 1))

Solution (Python):
import sys
import itertools

class RSQ:
    def __init__(self, n):
        self.sz = 1
        self.inf = (1 << 31) - 1
        while self.sz <= n: self.sz = self.sz << 1
        self.dat = [0] * (2 * self.sz - 1)
    
    def update(self, idx, x):
        idx += self.sz - 1
        self.dat[idx] += x
        while idx > 0:
            idx = (idx - 1) >> 1
            self.dat[idx] += x
            
    def query(self, a, b):
        return self.query_help(a, b, 0, 0, self.sz)
            
    def query_help(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        elif a <= l and r <= b:
            return self.dat[k]
        else:
            return self.query_help(a, b, 2 * k + 1, l, (l + r)>>1) + \
                    self.query_help(a, b, 2 * k + 2, (l + r) >> 1, r)
    
    
if __name__ == '__main__':
    line = sys.stdin.readline()
    n, q = line.split()
    n, q = int(n), int(q)
    rmq = RSQ(n)
    
    for i in range(q):
        line = sys.stdin.readline()
        op, a, b = line.split()
        op, a, b = int(op), int(a), int(b)
        if op == 0: 
            rmq.update(a, b)
        else: 
            sys.stdout.write(str(rmq.query(a, b + 1)) + '\n')

Solution (Python):
class RangeSumQuery(object):

    def __init__(self, size):
        self.size = 1
        while self.size <= size:
            self.size *= 2
        self.data = [0] * (self.size*2+2)

    def add(self, idx, value):
        k = idx + self.size - 1
        self.data[k] += value
        while k > 0:
            k = (k - 1) / 2
            self.data[k] += value

    def get_sum(self, start, end):
        def query(k, left, right):
            if right <= start or end <= left:
                return 0
            if start <= left and right <= end:
                return self.data[k]
            vl = query(k*2+1, left, (left+right)/2)
            vr = query(k*2+2, (left+right)/2, right)
            return sum([vl, vr])
        return query(0, 0, self.size)


def main():
    n, q = map(int, raw_input().split())
    rsq = RangeSumQuery(n)
    for _ in xrange(q):
        com, x, y = map(int, raw_input().split())
        if com == 0:
            rsq.add(x, y)
        else:
            print rsq.get_sum(x, y+1)

if __name__ == "__main__":
    main()

Solution (Python):
class RangeSumQuery(object):

    def __init__(self, size):
        self.size = 1
        while self.size <= size:
            self.size *= 2
        self.data = [0] * (self.size*2-1)

    def add(self, idx, value):
        k = idx + self.size - 1
        self.data[k] += value
        while k > 0:
            k = (k - 1) / 2
            self.data[k] += value

    def get_sum(self, start, end):
        def query(k, left, right):
            if right <= start or end <= left:
                return 0
            if start <= left and right <= end:
                return self.data[k]
            vl = query(k*2+1, left, (left+right)/2)
            vr = query(k*2+2, (left+right)/2, right)
            return vl + vr
        return query(0, 0, self.size)


def main():
    n, q = map(int, raw_input().split())
    rsq = RangeSumQuery(n)
    for _ in xrange(q):
        com, x, y = map(int, raw_input().split())
        if com == 0:
            rsq.add(x, y)
        else:
            print rsq.get_sum(x, y+1)

if __name__ == "__main__":
    main()

Solution (Python):
class RangeSumQuery(object):

    def __init__(self, size):
        self.size = 1
        while self.size <= size:
            self.size *= 2
        self.data = [0 for _ in xrange(self.size*2-1)]

    def add(self, idx, value):
        k = idx + self.size - 1
        self.data[k] += value
        while k > 0:
            k = (k - 1) / 2
            self.data[k] += value

    def get_sum(self, start, end):
        def query(k, left, right):
            if right <= start or end <= left:
                return 0
            if start <= left and right <= end:
                return self.data[k]
            vl = query(k*2+1, left, (left+right)/2)
            vr = query(k*2+2, (left+right)/2, right)
            return vl + vr
        return query(0, 0, self.size)


def main():
    n, q = map(int, raw_input().split())
    rsq = RangeSumQuery(n)
    for _ in xrange(q):
        com, x, y = map(int, raw_input().split())
        if com == 0:
            rsq.add(x, y)
        else:
            print rsq.get_sum(x, y+1)

if __name__ == "__main__":
    main()

Solution (Python):
import math
class segment_tree:
    
    
    
    def __init__(self, dat, query, default=0):
        self.offset = 2 ** math.ceil(math.log(len(dat), 2))
        self.table = [default] * self.offset + dat + [default] * (self.offset - len(dat))
        self.query = query
        for i in reversed(range(1, self.offset)):
            self.table[i] = self.query((self.table[2 * i], self.table[2 * i + 1]))

    
    def find(self, l, r):
        return self.query(self.__range(l,r))

    def __range(self, l, r):
        l += self.offset
        r += self.offset
        while l <= r:
            if l & 1:
                yield self.table[l]
                l += 1
            l >>= 1
            if r & 1 == 0:
                yield self.table[r]
                r -= 1
            r >>= 1
        
    def update(self, i, x, function=lambda a, b:b):
        i += self.offset
        self.table[i] = function(self.table[i], x)
        while 1 < i:
            i >>= 1
            self.table[i] = self.query((self.table[2 * i], self.table[2 * i + 1]))

from sys import stdin
readline = stdin.readline


n, q = map(int, readline().split())

rmq = segment_tree([0] * n, sum, default=0)
from operator import add
function = (lambda x, y:rmq.update(x - 1, y, add), lambda x, y:print(rmq.find(x - 1, y - 1)))
for com, x, y in (map(int, readline().split()) for _ in range(q)):
    function[com](x, y)

Solution (Python):
class BIT:
    def __init__(self, size):
        self.size = size
        self.bit = [0] * (size + 1)

    
    def sum(self, i):
        s = 0
        while (i > 0):
            s += self.bit[i]
            i -= i & -i
        return s

    
    def sum_sec(self, i, j):
        return self.sum(j) - self.sum(i)

    def add(self, i, x):
        i += 1
        while (i <= self.size):
            self.bit[i] += x
            i += i & -i

n, q = map(int, raw_input().split())
bit = BIT(n)
for i in xrange(q):
    c, x, y = map(int, raw_input().split())
    if c == 0: bit.add(x - 1, y)
    else: print bit.sum_sec(x - 1, y)

Solution (Python):
import math
class FenwickTree:
    """
    FenwickTree(Binary Indexed Tree)
    total number: n
    queries:
    1. add(i, val): add val to i-th value 
    2. sum(n): sum(bit[0] + ... + bit[n-1])
    complexity: O(log n)

    Self-balancing binary search tree or Segment Tree can do the same, it takes longer to program and complexity also increases.
    Thanks: http://hos.ac/slides/20140319_bit.pdf
    
    used in ARC031 C, indeednow finalB E
    """
    def __init__(self, a_list):
        
        self.N = len(a_list)
        self.bit = a_list[:]
        for _ in range(N, 1<<(math.ceil(math.log(N, 2)))): self.bit.append(0)
        for i in range(self.N-1):
            self.bit[i | (i+1)] += self.bit[i]

    def add(self, i, val):
        while i < self.N:
            self.bit[i] += val
            i |= i + 1

    def sum(self, n):
        ret = 0
        while n >= 0:
            ret += self.bit[n]
            n = (n & (n + 1)) - 1
        return ret

N, Q = map(int, input().split())
bit = FenwickTree([0]*N)
for _ in range(Q):
    com, x, y = map(int, input().split())
    if com == 0:
        bit.add(x-1, y)
    elif com == 1:
        print(bit.sum(y-1) - bit.sum(x-2))

Solution (Python):
from math import sqrt, ceil

n, q = map(int, input().split())
unit = ceil(sqrt(n))

l = [(0, [0] * unit) for _ in range(unit)]

while q:
    op, s, t = map(int, input().split())
    s -= 1
    sd, sm = s // unit, s % unit
    if op:
        t -= 1
        td, tm = t // unit, t % unit
        if sd == td:
            print(sum(l[sd][1][sm:tm + 1]))
        else:
            unit_sum = sum((tup[0] for tup in l[sd + 1:td]))
            s_sum = sum(l[sd][1][sm:])
            t_sum = sum(l[td][1][:tm + 1])
            print(unit_sum + s_sum + t_sum)
    else:
        tup = l[sd]
        tup[1][sm] += t
        l[sd] = (tup[0] + t, tup[1])
    q -= 1

Solution (Python):

import math


n, q = map(int, input().split())
b_size = math.ceil(math.sqrt(n))
b_len = math.ceil(n/b_size)
a = [0 for i in range(n)]
b = [min(a[b_size * i:b_size * (i + 1)]) for i in range(b_len)]
for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        x -= 1
        
        a[x] += y
        
        index = x // b_size
        
        b[index] += y

    else:
        x -= 1
        y -= 1
        
        target = []
        x_index = x // b_size
        y_index = y // b_size
        x_mod = x % b_size
        y_mod = y % b_size
        if x_index == y_index:
            target.extend(a[x:y + 1])
        else:
            if x_mod == 0:
                target.append(b[x_index])
            else:
                target.extend(a[x:(x_index + 1) * b_size])

            if y_mod == b_size - 1:
                target.append(b[y_index])
            else:
                target.extend(a[y_index * b_size:y + 1])

            if x_index + 1 <= y_index - 1:
                target.append(sum(b[x_index + 1 : y_index]))
        print(sum(target))

Solution (Python):
N, Q = [int(x) for x in raw_input().split()]

class Node:

    def __init__(self, x, y):
        self.value = 0
        self.x = x
        self.y = y
        self.l = self.r = None

        if y - x > 1:
            mid = (x + y) / 2
            self.l = Node(x, mid)
            self.r = Node(mid, y)

    def add(self, i, x):
        if self.x <= i < self.y:
            self.value += x
            if self.l:
                self.l.add(i, x)
            if self.r:
                self.r.add(i, x)

    def sum(self, x, y):
        if y <= self.x or self.y <= x:
            return 0
        if x <= self.x and self.y <= y:
            return self.value
        return self.l.sum(x, y) + self.r.sum(x, y)

t = Node(0, N)

for _ in xrange(Q):
    com, x, y = [int(s) for s in raw_input().split()]
    if com == 0:
        t.add(x-1, y)
    if com == 1:
        print t.sum(x-1, y)

Solution (Python):
class BIT(object):

    def __init__(self, size, init_data=None):
        self.size = size
        if init_data is None:
            init_data = [0] * (size + 1)
        self.data = init_data

    def sum(self, idx):
        ret = 0
        while idx > 0:            
            ret += self.data[idx]
            idx -= idx & -idx 
        return ret

    def add(self, idx, value):
        while idx <= self.size:
            self.data[idx] += value
            idx += idx & -idx

if __name__ == "__main__":
    n, q = list(map(int, input().split()))
    bit = BIT(n)
    for _ in range(q):
        com, x, y = list(map(int, input().split()))
        if com == 0:
            bit.add(x, y)
        else:
            print(bit.sum(y)-bit.sum(x-1))

Solution (Python):
from array import array

class BIT(object):

    def __init__(self, size, init_data=None):
        self.size = size
        if init_data is None:
            init_data = [0] * (size + 1)
        self.data = array("q", init_data)

    def sum(self, idx):
        ret = 0
        while idx > 0:            
            ret += self.data[idx]
            idx -= idx & -idx 
        return ret

    def add(self, idx, value):
        while idx <= self.size:
            self.data[idx] += value
            idx += idx & -idx

if __name__ == "__main__":
    n, q = list(map(int, input().split()))
    bit = BIT(n)
    for _ in range(q):
        com, x, y = list(map(int, input().split()))
        if com == 0:
            bit.add(x, y)
        else:
            print(bit.sum(y)-bit.sum(x-1))

Solution (Python):
n, q = map(int, raw_input().split())
n0 = 2**n.bit_length()
data = [0]*(n0*2)
def add(k, a):
    k += n0 - 1
    data[k] += a
    while k:
        k = (k - 1) / 2
        data[k] += a
def query(a, b, k, l, r):
    if b <= l or r <= a:
        return 0
    if a <= l and r <= b:
        return data[k]
    vl = query(a, b, 2*k+1, l, (l + r) / 2)
    vr = query(a, b, 2*k+2, (l + r) / 2, r)
    return vl + vr
def getSum(s, t):
    print query(s, t+1, 0, 0, n0)
for i in xrange(q):
    com, x, y = map(int, raw_input().split())
    [add, getSum][com](x, y)

Solution (Python):
import sys
import math

f_i = sys.stdin

n, q = map(int, f_i.readline().split())


n = 2 ** math.ceil(math.log(n, 2))

A = [0 for i in range(2 * n - 1)]


def add(i, x):
    
    i += n - 2
    A[i] += x

    while i > 0:
        i = (i - 1) // 2
        A[i] += x

def getSum(s, t, k, l, r):
    if r < s or t < l:
        return 0
    elif s <= l and r <= t:
        return A[k]
    else:
        mid = (l + r) // 2
        lsum = getSum(s, t, k * 2 + 1, l, mid)
        rsum = getSum(s, t, k * 2 + 2, mid + 1, r)
        return lsum + rsum

for s_i in f_i:
    com, x, y = map(int, s_i.split())
    if com == 0:
        add(x, y)
    else:
        ans = getSum(x, y, 0, 1, n)
        print(ans)

Solution (Python):



class FenwickTree(object):

    def __init__(self, num_elems):
        self.num_elems = num_elems
        self.data = [0 for _ in range(num_elems)]

    def sum_to(self, end):
        s = 0
        i = end - 1
        while i >= 0:
            s += self.data[i]
            i = (i & (i + 1)) - 1
        return s

    def sum_range(self, start, end):
        return self.sum_to(end) - self.sum_to(start)

    def add(self, idx, x):
        while idx < self.num_elems:
            self.data[idx] += x
            idx |= idx + 1


def main():
    n, q = map(int, input().split())
    ft = FenwickTree(n)
    for _ in range(q):
        c, x, y = map(int, input().split())
        if c == 0:
            ft.add(x - 1, y)
        elif c == 1:
            print(ft.sum_range(x - 1, y))


if __name__ == '__main__':
    main()

Solution (Python):
import math
def update(index,y):
    targ[index] += y
    index = (index - 1) // 2
    while True:
        targ[index] = targ[index*2 + 1] + targ[index*2 + 2]
        if index <= 0:
            break
        index = (index - 1) // 2

def find(ini,end,node,inode,enode):
    
    if ini > enode or inode > end:
        return 0
    elif (inode >= ini and end >= enode) or inode == enode:
        return targ[node]
    else:
        ininum = find(ini,end,node*2 + 1,inode,(inode+enode)//2)
        endnum = find(ini,end,node*2 + 2,(inode+enode)//2 + 1,enode)
        return ininum + endnum

num,query = (int(n) for n in input().split(' '))
ln = 2 ** math.ceil(math.log2(num)) - 1
if num == 1:
    tail = 2
else:
    tail = 2 ** math.ceil(math.log2(num)) - num
targ = [0] * (ln + num + tail)
for q in range(query):
    
    qtype,temp1,temp2 = (int(n) for n in input().split(' '))
    if qtype == 0:
        update(temp1+ln-1,temp2)
    else:
        print(find(temp1-1,temp2-1,0,0,ln))