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 BIT():
	def __init__(self, n):
		self.n = n
		self.bit = [0]*(n+1)
	
	def getsum(self, k):
		ret = 0
		while k:
			ret += self.bit[k]
			k -= k&-k
		return ret
		
	def p_sum(self, i, j):
		return self.getsum(j)-self.getsum(i-1)
		
	def add(self, k, x):
		while k <= n:
			self.bit[k] += x
			k += k&-k

n,q = map(int,input().split())
BIT = BIT(n)
for _ in range(q):
	c,x,y = map(int,input().split())
	if c==0:
		BIT.add(x,y)
	else:
		print(BIT.p_sum(x,y))

Solution (Python):
class BIT:
  def __init__(self, size):
    self.tree = [0] * (size + 1)
    self.size = size
  
  def sum(self, a):
    res = 0
    a += 1
    while a:
      res += self.tree[a]
      a -= a & -a
    return res
  def add(self, a, x):
    a += 1
    while a < len(self.tree):
      self.tree[a] += x
      a += a & -a

import sys

stdin = sys.stdin
na = lambda: map(int, stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())

def main():
  n, q = na()
  bit = BIT(n)
  for _ in range(q):
    t, x, y = na()
    if t == 0:
      bit.add(x - 1, y)
    else:
      print(bit.sum(y - 1) - bit.sum(x - 2))

main()

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]

class Rsum():
	def __init__(self, size):
		
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [0 for _ in range(2*self.n-1)]

	def Access(self, x):
		return self.node[x+self.n-1]

	def Add(self, x, val):
		x += self.n-1
		self.node[x] += val
		while x > 0:
			x = (x-1)//2
			self.node[x] = self.node[2*x+1] + self.node[2*x+2]
		return

	
	def Get(self, a, b, k=0, l=0, r=-1):
		if r < 0:
			r = self.n

		if a >= r or b <= l:
			return 0
		elif a <= l and b >= r:
			return self.node[k]
		else:
			vl = self.Get(a, b, 2*k+1, l, (l+r)//2)
			vr = self.Get(a, b, 2*k+2, (l+r)//2, r)
			return vl + vr

n, q = map(int, input().split())
SegT = Rsum(n)
for _ in range(q):
	c, x, y = map(int, input().split())
	if c == 0:
		SegT.Add(x-1, y)
	else:
		print(SegT.Get(x-1, y))

Solution (Python):
class RSQ(object):
    INIT = 0

    def __init__(self, num) -> None:
        n = 1
        while n <= num:
            n = n * 2
        self.n = n
        self.val = [self.INIT] * (2 * n - 1)

    @staticmethod
    def merge(a: int, b: int) -> int:
        return a + b

    def update(self, k: int, x: int) -> None:
        k = k + self.n - 1
        self.val[k] += x
        while k:
            k = (k - 1) // 2
            self.val[k] = self.merge(self.val[k * 2 + 1], self.val[k * 2 + 2])

    def dfs(self, beg: int, end: int, k: int, l: int, r: int) -> int:
        if (end <= l or r <= beg):
            return self.INIT
        if (beg <= l and r <= end):
            return self.val[k]
        vl = self.dfs(beg, end, k * 2 + 1, l, (l + r) // 2)
        vr = self.dfs(beg, end, k * 2 + 2, (l + r) // 2, r)
        return self.merge(vl, vr)

    def query(self, beg: int, end: int) -> int:
        return self.dfs(beg, end, 0, 0, self.n)


if __name__ == "__main__":
    n, q = map(lambda x: int(x), input().split())
    rmq = RSQ(n)

    for _ in range(q):
        com, x, y = map(lambda x: int(x), input().split())
        if (0 == com):
            rmq.update(x, y)
        else:
            print(rmq.query(x, y + 1))

Solution (Python):
class SegmentTree():
    """一点加算、区間取得クエリをそれぞれO(logN)で答えるデータ構造を構築する
    add: i番目にvalを加える
    get_sum: 区間[begin, end)の和を求める
    """
    def __init__(self, n):
        self.n = n
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [0] * (2*self.size - 1)

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

    def get_sum(self, begin, end):
        begin += (self.size - 1)
        end += (self.size - 1)
        s = 0
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                s += self.node[end]
            if (begin - 1) & 1:
                s += self.node[begin]
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2
        return s

    def debug(self):
        """Segment Tree上の葉の配列を出力する"""
        return(self.node[self.size - 1: self.size - 1 + self.n])


n, q = map(int, input().split())
info = [list(map(int, input().split())) for i in range(q)]
st = SegmentTree(n)
 
for i in range(q):
    com, x, y = info[i]
    if com == 0:
        st.add(x - 1, y)
    else:
        print(st.get_sum(x - 1, y))

Solution (Python):
n,q=map(int,input().split())
bit=[0]*(n+1)
def add(a,w):
    x=a
    while(x<=n):
        bit[x]+=w
        x+=x&(-x)
def sum(a):
    ret=0
    x=a
    while(x>0):
        ret+=bit[x]
        x-=x&(-x)
    return ret
for j in range(q):
    com,x,y=map(int,input().split())
    if com==0:
        add(x,y)
    else:
        print(sum(y)-sum(x-1))

Solution (Python):
class SegmentTree:
    
    def __init__(self, n):
        self.n = n
        self.T = [0 for _ in range(2*n-1)]
        
    def add(self, i, x):
        i += self.n - 1
        self.T[i] += x
        while(i > 0):
            i = (i - 1) // 2
            self.T[i] += x
            
    def get_sum(self, a, b, k, l, r):
        if r<= a or b<= l:
            return 0
        if a <= l and r <= b:
            return self.T[k]
        vl = self.get_sum(a, b, k*2+1, l,(l+r)//2)
        vr = self.get_sum(a, b, k*2+2, (l+r)//2,r)
        return vl + vr
    

n_, q = [int(i) for i in input().split()]
n = 1
while(n < n_):
    n *= 2
T = SegmentTree(n)
for _ in range(q):
    c, x, y = [int(i) for i in input().split()]
    if c == 0:
        T.add(x - 1, y)
    else:
        print(T.get_sum(x - 1, y, 0, 0, n))

Solution (Python):
line = input()
n, q = list(map(int, line.split()))
N = 1
while N < n + 1:
    N *= 2
a = [0 for _ in range(0, 2 * N - 1)]

def update(k, v):
    k += N - 1
    a[k] += v
    while k > 0:
        k = (k - 1) // 2
        a[k] = a[k * 2 + 1] + a[k * 2 + 2]

def query(x, y, k, l, r):
    if r <= x or y <= l:
        return 0
    elif x <= l and r <= y:
        return a[k]
    m = (l + r) // 2
    return query(x, y, k * 2 + 1, l, m) + query(x, y, k * 2 + 2, m, r)

for _ in range(0, q):
    line = input()
    c, x, y = list(map(int, line.split()))
    if c == 0:
        update(x, y)
    elif c == 1:
        ans = query(x, y + 1, 0, 0, N)
        print(ans)

Solution (Python):


import sys
from operator import add

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 SegTree:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_val: 区間[l, r)の値を得る
    """
 
    def __init__(self, n, func, init):
        """
        :param n: 要素数
        :param func: 値の操作に使う関数(min, max, addなど)
        :param init: 要素の初期値
        """
        self.n = n
        self.func = func
        self.init = init
        
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.init] * (n2 << 1)
 
    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 1:
            self.tree[i >> 1] = x = self.func(x, self.tree[i ^ 1])
            i >>= 1
 
    def get_val(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        return self._get_val(a, b, 1, 0, self.n2)
 
    def _get_val(self, a, b, k, l, r):
        """
        [a, b)の値を得る内部関数
        :param k: 現在調べている区間のtree内index
        :param l, r: kが表す区間の左右端index [l, r)
        :return: kが表す区間と[a, b)の共通区間内での最小値。共通区間を持たない場合は初期値
        """
        
        if r <= a or b <= l:
            return self.init
        
        if a <= l and r <= b:
            return self.tree[k]
        
        m = (l + r) // 2
        return self.func(
            self._get_val(a, b, k << 1, l, m),
            self._get_val(a, b, (k << 1) + 1, m, r)
        )

N,Q=MAP()

st=SegTree(N+1, add, 0)
for _ in range(Q):
    com,x,y=MAP()
    if com==0:
        st.update(x, y+st.get_val(x, x+1))
    else:
        print(st.get_val(x, y+1))

Solution (Python):
class SegmentTree:
    def __init__(self, lst, op, e):
        self.n = len(lst)
        self.N = 2**((self.n-1).bit_length())
        self.op = op 
        self.e = e 
        self.v = [None]*(2*self.N-1)
        
        
        for i in range(self.N):
            self.v[i + self.N - 1] = lst[i] if i < self.n else self.e
        for i in range(self.N - 2, -1, -1):
            self.v[i] = self.op(self.v[2*i + 1], self.v[2*i + 2])
        
    
    def update(self, i, x):
        i += self.N - 1
        self.v[i] += x
        while i > 0:
            i -= 1
            i >>= 1
            self.v[i] = self.op(self.v[2*i + 1], self.v[2*i+2])
    
    
    def query(self, l, r):
        assert l < r
        left = l + self.N - 1
        right = r + self.N - 1
        L = self.e
        R = self.e
        while left < right:
            if left % 2 == 0: 
                L = self.op(L, self.v[left])
                left += 1
            if right % 2 == 0: 
                right -= 1
                R = self.op(self.v[right], R)
            left -= 1
            left >>= 1
            right >>= 1
        return self.op(L, R)

n, q = map(int, input().split())
A = [0]*n
st = SegmentTree(A, lambda x, y: x+y, 0)
for _ in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        st.update(x-1, y)
    else:
        print(st.query(x-1, y))

Solution (Python):

n, q = map(int, input().split())
size = 1
while size < n:
    size *= 2
size = size
seg_tree = [0]*(size*2)

def update(i, x):
    ind = size-1+i
    seg_tree[ind] += x
    while ind>1:
        ind = ind//2
        left = seg_tree[ind*2]
        right = seg_tree[ind*2+1]
        seg_tree[ind] = left + right

def _find(s,t,i,l,r):
    if r < s or t < l:return 0
    if s <= l and r <= t:
        return seg_tree[i]
    else:
        left = _find(s,t,i*2,l, (l+r)//2)
        right = _find(s,t,i*2+1,(l+r)//2+1,r)
        return left+right

def find(s,t):
    return _find(s,t,1,1,size)

for _ in range(q):
    com, x, y = map(int, input().split())
    if not com:
        update(x, y)
    else:
        print(find(x,y))

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

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

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

    def reset(self):
        self.bit = [0] * (self.n + 1)


N, Q = map(int, input().split())
BIT = BinaryIndexedTree(N)
for q in range(Q):
    com, x, y = map(int, input().split())
    if com == 0:
        BIT.add(x, y)
    if com == 1:
        print(BIT.sum(y) - BIT.sum(x - 1))

Solution (Python):
'''
セグメント木
配列バージョン
'''

N, Q = map(int, input().split())
pn = 1
while pn < N:
    pn *= 2
N = pn
A = [0]*(2*N-1)


def add(x, y):
    n = N+x-1
    A[n] += y
    while n > 0:
        n = (n-1)//2
        A[n] += y


def getSum(k, x, y, s, t):
    '''
    範囲[x,y)
    区間[s,t)
    '''
    
    
    if x >= t or y <= s:
        
        return 0
    
    if x <= s and t <= y:
        
        return A[k]

    
    
    lv = getSum(2*k+1, x, y, s, (s+t)//2)
    rv = getSum(2*k+2, x, y, (s+t)//2, t)
    return lv+rv


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

Solution (Python):
import math


def update(numlist,i):
  if i<0:
    return
  if i==0:
    numlist[i]=numlist[2*i+1]+numlist[2*i+2]
    return
  numlist[i]=numlist[2*i+1]+numlist[2*i+2]
  update(numlist,(i-1)//2)
  return

def find(numlist,x,y,k,minimum,maximum):
  if x>=maximum or y<minimum:
    return 0
  if x<=minimum and maximum-1<=y:
    return numlist[k]
  else:
    L=find(numlist,x,y,k*2+1,minimum,(maximum+minimum)//2)
    R=find(numlist,x,y,k*2+2,(maximum+minimum)//2,maximum)
    return L+R
    
  

n,q=map(int,input().split())
L2n=math.ceil(math.log2(n))
zero=2**(L2n)-1
MAX=2**31-1
numlist=[0]*(2**(L2n+1)-1)
resultlist=[]

for _ in range(0,q):
  com,x,y=map(int,input().split())
  if com:
    resultlist.append(find(numlist,x-1,y-1,0,0,2**L2n))
  else:
    numlist[zero+x-1]+=y
    update(numlist,(zero+x-2)//2)

for x in resultlist:
  print (x)

Solution (Python):
class SegTree:
    '''Segment Tree:
    Data structure to answer queries on segments of a sequence.
    '''
    def __init__(self,n,init_num,func):
        '''Create a segment tree.
        :param n: Size
        :type n: int or float (number)
        :param init_num: Initialization number
        :type init_num: int or float (number)
        :param func: Function to use
        :type func: function
        '''
        self.func=func
        self.init_num=init_num
        self.size = 2**(len(bin(n-1))-2)*2-1
        self.tree = [init_num for i in range(self.size)]
     
    def data(self):
        '''Return data.
        '''
        return self.tree[self.size//2:]
 
    def update(self,i,x,update_func):
        '''Update the i-th data by update_func.
            example:
            a[i]<-update_func(a[i],x)
        '''
        i=self.size//2+i
        self.tree[i]=update_func(self.tree[i],x)
        while 1:
            i=(i-1)//2
            self.tree[i]=self.func(self.tree[i*2+1],self.tree[i*2+2])
            if i<=0:
                break
 
    def _check(self,s,t,l,r,_p=0):
        if s<=l and r<=t:
            return self.tree[_p]
        elif r<s or t<l:
            return self.init_num
        else:
            return self.func(self._check(s,t,l,l+(r-l)//2,_p*2+1),self._check(s,t,l+(r-l)//2+1,r,_p*2+2))
 
    def find(self,s,t):
        '''Answer queries on [s,t]segment
        '''
        return self._check(s,t,0,self.size//2)

n,q=map(int,input().split())
st=SegTree(n,0,lambda x,y:x+y)
for i in range(q):
    c,x,y=map(int,input().split())
    if c:
        print(st.find(x-1,y-1))
    else:
        st.update(x-1,y,lambda x,y:x+y)

Solution (Python):
n,q=map(int,input().split())
Q=[list(map(int,input().split())) for i in range(q)]


for i in range(30):
    if n<1<<i:
        seg_el=1<<i
        break

SEG=[0]*(2*seg_el-1)

def update(n,x,seg_el):
    i=n+seg_el-1
    SEG[i]+=x
    i=(i-1)//2
    
    while i>=0:
        SEG[i]+=x
        i=(i-1)//2
        
def getvalues(a,b,k,l,r):
    if r<=a or b<=l:
        return 0
    if a<=l and r<=b:
        return SEG[k]
    vl=getvalues(a,b,k*2+1,l,(l+r)//2)
    vr=getvalues(a,b,k*2+2,(l+r)//2,r)
    return vl+vr

for com,x,y in Q:
    if com==0:
        update(x,y,seg_el)
    else:
        print(getvalues(x,y+1,0,0,seg_el))

Solution (Python):
class BIT():
    """数列aに対して以下の操作がO(log n) でできる
    - add(i,x): a[i] += x
    - sum_1_to_i(i): 区間[1, i]のaの総和
    
    sum_i_to_j(i,j): 区間[i,j]のaの総和
    数列aは0に初期化されているとする"""
    def __init__(self, n:int):
        self.n = n
        self.bit = [0]*(n+1)
        
    def add(self, i:int, x:int):
        """i番目(1-idexed)にxを加算"""
        while i<=self.n:
            self.bit[i] += x
            i += i&-i
            
    def sum_1_to_i(self, i:int)->int: 
        """1番目からi番目(含む)までの総和"""
        s=0
        while i>0:
            s += self.bit[i]
            i -= i&-i
        return s
    
    def sum_i_to_j(self, i:int, j:int):
        """i番目からj番目(含む)までの総和"""
        return self.sum_1_to_i(j) - self.sum_1_to_i(i-1)
    

n,q = map(int, input().split())
bit = BIT(n)
for _ in range(q):
    com,x,y = map(int, input().split())
    if com==0:
        bit.add(x,y)
    else:
        print(bit.sum_i_to_j(x,y))

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

class BIT(object):
    def __init__(self, size: int):
        self.bitree = [0]*(size+1)
        
    def setval(self, idx:int, val:int):
        tree = self.bitree
        nex_idx = idx+1
        
        while nex_idx < len(tree):
            tree[nex_idx] += val
            nex_idx += nex_idx & -nex_idx
            
    def getsum(self, idx: int):
        tree, result = self.bitree, 0
        nex_idx = idx+1
        
        while nex_idx:
            result += tree[nex_idx]
            nex_idx -= nex_idx & -nex_idx
            
        return result
    
n,q = li()
bitree = BIT(n)

for _ in range(q):
    com, x, y = li()
    if com == 0:
        bitree.setval(x-1, y)
    else:
        print(bitree.getsum(y-1) - bitree.getsum(x-2))

Solution (Python):
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i+1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  
        return str(list(self))

    def sum(self, i: int):
        
        if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i: int, x):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def __getitem__(self, key):
        if not (0 <= key < self.size): raise IndexError("error!")
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])

N, Q = map(int, input().split())
bit = Bit(N+1)
for i in range(Q):
    com, x, y = map(int, input().split())
    if com == 0:
        bit.add(x, y)
    else:
        print(bit.sum(y+1) - bit.sum(x))

Solution (Python):
from array import array
import bisect
import collections
import heapq
import itertools
import operator
import sys


class BIT:
    def __init__(self, n):
        self.n = n
        self.arr = array("l", [0] * (n + 1))

    def __str__(self):
        return str(self.arr.tolist())

    def add(self, i, x):
        while i <= self.n:
            self.arr[i] += x
            i += i & -i

    def sum(self, i, j=None):
        if j is None:
            s = 0
            while i > 0:
                s += self.arr[i]
                i -= i & -i
            return s

        if i > j:
            raise ValueError

        return self.sum(j) - self.sum(i - 1)


def main():
    n, q = map(int, sys.stdin.readline().split())
    bit = BIT(n)

    for _ in range(q):
        query, x, y = map(int, sys.stdin.readline().split())
        if query == 0:
            bit.add(x, y)
        elif query == 1:
            print(bit.sum(x, y))
        else:
            raise ValueError


if __name__ == "__main__":
    main()