Problem:
 Score : 100 points    Problem Statement You are given an array a_0, a_1, ..., a_{N-1} of length N . Process Q queries of the following types.   0 p x : a_p \gets a_p + x  1 l r : Print \sum_{i = l}^{r - 1}{a_i} .       Constraints  1 \leq N, Q \leq 500,000  0 \leq a_i, x \leq 10^9  0 \leq p < N  0 \leq l_i < r_i \leq N  All values in Input are integer.         Input Input is given from Standard Input in the following format:  N  Q  a_0  a_1 ... a_{N - 1}  \textrm{Query}_0  \textrm{Query}_1 : \textrm{Query}_{Q - 1}       Output For each query of the latter type, print the answer.        Sample Input 1 5 5
1 2 3 4 5
1 0 5
1 2 4
0 3 10
1 0 5
1 0 3      Sample Output 1 15
7
25
6

Solution (Python):
from copy import *
import sys
S=sys.stdin.readlines()

def init(N,node,unit,func):
  n=1
  while n<N:
    n<<=1
  for i in range(n*2-1):
    if len(node)<=i:
      node.append(deepcopy(unit))
    else:
      node[i]=deepcopy(unit)
  node.append(func)
  node.append(unit)
  node.append(n)

def upd(node,x,a):
  y=node[-1]+x
  node[y-1]=a
  while y>1:
    y=y>>1
    node[y-1]=node[-3](node[(y<<1)-1],node[y<<1])

def query(node,l,r):
  x,y=l,r
  z=node[-1]-1
  r=node[-2]
  while True:
    if x==y:
      return r
    if x&1:
      r=node[-3](r,node[x+z])
      x+=1
    if y&1:
      r=node[-3](r,node[y+z-1])
    x>>=1
    y>>=1
    z>>=1
    if z==0:
      return r

def bis_min_k(node,k,cond):
  x=k+1
  while True:
    if node[-1]<=x:
      return x-node[-1]
    if cond(node[(x<<1)-1]):
      x=x<<1
    else:
      x=(x<<1)+1

def bis_min(node,l,r,cond):
  x,y=l,r
  z=node[-1]-1
  for i in range(30):
    if x+(1<<i)>y:
      break
    if x&(1<<i):
      if cond(node[z+(x>>i)]):
        return bis_min_k(node,z+(x>>i),cond)
      x+=(1<<i)
    if z==0:
      break
    z>>=1
  for i in range(29,-1,-1):
    if i and ((node[-1]-1)>>(i-1))==0:
      continue
    if x+(1<<i)>y:
      continue
    if (y-x)&(1<<i):
      if cond(node[((node[-1]-1)>>i)+(x>>i)]):
        return bis_min_k(node,((node[-1]-1)>>i)+(x>>i),cond)
      x+=(1<<i)
  return node[-1]

N,Q=map(int,S[0].split())
A=list(map(int,S[1].split()))
X=[]
init(N+1,X,0,lambda x,y:x+y)
for i in range(N):
  upd(X,i,A[i])
a,b,c=0,0,0
for i in range(Q):
  a,b,c=map(int,S[i+2].split())
  if a:
    print(query(X,b,c))
  else:
    upd(X,b,X[X[-1]+b-1]+c)

Solution (Python):
code = r"""




cdef extern from "/opt/atcoder-stl/atcoder/fenwicktree.hpp" namespace "atcoder":
    cdef cppclass fenwick_tree[T]:
        fenwick_tree(int n)
        void add(int p, T x)
        T sum(int l, int r)

from libc.stdio cimport scanf, printf
cdef int n, q, i, a, t, u, v
scanf('%d%d', &n, &q)
cdef fenwick_tree[long] *bit = new fenwick_tree[long](n)
for i in range(n):
    scanf('%d', &a)
    bit.add(i, a)
for i in range(q):
    scanf('%d%d%d', &t, &u, &v)
    if t:
        printf('%ld\n', bit.sum(u, v))
    else:
        bit.add(u, v)
"""
import os
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
import sys
from random import *
from collections import *
from heapq import *

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij = [(1, 0), (-1, 0), (0, 1), (0, -1)]



class BitSum:
    def __init__(self, n):
        self.n = n+1
        self.table = [0]*self.n

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

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

    
    def sumlr(self, l, r):
        if l == r: return 0
        if l == 0: return self.sum(r-1)
        return self.sum(r-1)-self.sum(l-1)

    
    
    def rank(self, x):
        idx = 0
        for lv in range((self.n-1).bit_length()-1, -1, -1):
            mid = idx+(1 << lv)
            if mid >= self.n: continue
            if self.table[mid] < x:
                x -= self.table[mid]
                idx += 1 << lv
        return idx

n,q=MI()
aa=LI()
bit=BitSum(n)
for i,a in enumerate(aa):bit.add(i,a)
for _ in range(q):
    t,a,b=MI()
    if t:print(bit.sumlr(a,b))
    else:bit.add(a,b)

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${@q!EWL(6ukQ@o>Y}4C6HEoS)r!K{Q_>gtH{_6Saob;JGAWA?{fmdfx-dH<9YLD;+H%Cmp*hsD!&3n^|qs1QL*`)JftU5Gu3fXbLo6l?o2C6W^@ofP
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
"""うしくん元気ですか



cimport numpy as np
from libc.stdio cimport scanf, printf
import numpy as np

cdef class BIT:
    cdef int n
    cdef np.ndarray data

    def __cinit__(BIT self, int n):
        self.n = n
        self.data = np.zeros(n + 1, np.int_)

    cdef void add(BIT self, int i, long x):
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    cdef long sum(BIT self, int i):
        cdef long s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

def main():
    cdef int n, q, a, i, t, u, v
    scanf('%d%d', &n, &q)
    cdef BIT bit = BIT(n)
    for i in range(n):
        scanf('%d', &a)
        bit.add(i + 1, a)
    for i in range(q):
        scanf('%d%d%d', &t, &u, &v)
        if t:
            printf('%ld\n', bit.sum(v) - bit.sum(u))
        else:
            bit.add(u + 1, v)
main()
"""

import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${rhO^=%}5WVv&Mp|ta6ariIQbnbQ9xC<TTU
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
N,Q=map(int,input().split())

A=[0]+list(map(int,input().split()))

LEN=N+1
BIT=[0]*(LEN+1) 

def update(v,w): 
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v)) 

def getvalue(v): 
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) 
    return ANS

for i in range(1,N+1):
    update(i,A[i])

for i in range(Q):
    q,p,x=map(int,input().split())
    if q==0:
        p+=1
        update(p,x)
    else:
        l=p+1
        r=x+1

        print(getvalue(r-1)-getvalue(l-1))

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,q = list(map(int, input().split()))


def init(bit, values):
    for i,v in enumerate(values):
        add(bit,i+1,v)

def query(bit,i):
    res = 0
    while i > 0:
        res += bit[i]
        i -= i&(-i)
    return res


def add(bit,i,x):
    if i==0:
        raise RuntimeError
    while i <= len(bit)-1:
        bit[i] += x
        i += i&(-i)
    return

def index(bit, v):
    """a1,...,aiの和がv以上になる最小のindexを求める
    存在しないとき配列サイズを返す
    """
    i = 0
    n = len(bit)-1
    k = 1<<((n-1).bit_length())
    while k>0:
        if i+k<n+1 and bit[i+k]<v:
            v -= bit[i+k]
            i += k
        k //= 2
    if v==1:
        return i+1
    else:
        return n+1
bit = [0]*(n+1)    
init(bit, list(map(int, input().split())))
for i in range(q):
    t,u,v = map(int, input().split())
    if t==0:
        add(bit, u+1, v)
    else:
        print(query(bit, v) - query(bit, u))

Solution (Python):
class BIT:
    def __init__(self,len_A):
        self.N = len_A + 10
        self.bit = [0]*(len_A+10)
        
    def query(self,i):
        res = 0
        idx = i+1
        while idx:
            res += self.bit[idx]
            idx -= idx&(-idx)
        return res

    def update(self,i,x):
        idx = i+1
        while idx < self.N:
            self.bit[idx] += x
            idx += idx&(-idx)
    
    def lower_left(self,w):
        if (w < 0):
            return -1
        x = 0
        k = 1<<(self.N.bit_length()-1)
        while k > 0:
            if x+k < self.N and self.bit[x+k] < w:
                w -= self.bit[x+k]
                x += k
            k //= 2
        return x
    
n, q = map(int, input().split())
a = list(map(int, input().split()))
bit = BIT(n)
for i in range(n):
    bit.update(i, a[i])

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

Solution (Python):
class BIT():

    __slots__ = ["n", "data"]

    def __init__(self, length_or_list):
        if isinstance(length_or_list, int):
            self.n = length_or_list + 1
            self.data = [0] * self.n
        else:
            self.n = len(length_or_list) + 1
            self.data = [0] + length_or_list
            for i in range(1, self.n):
                if i + (i & -i) < self.n:
                    self.data[i + (i & -i)] += self.data[i]        

    def point_append(self, index, delta):
        index += 1
        while index < self.n:
            self.data[index] += delta
            index += index & -index
        
    def prefix_folded(self, end):
        res = 0
        while end: 
            res += self.data[end]
            end -= end & -end
        return res

    def folded(self, begin, end):
        ret = 0
        while begin < end:
            ret += self.data[end]
            end -= end & -end
        while end < begin:
            ret -= self.data[begin]
            begin -= begin & -begin
        return ret

def main():
    import sys
    input = sys.stdin.buffer.readline

    N, Q = map(int, input().split())
    bit = BIT(list(map(int, input().split())))
    ans = []
    for _ in range(Q):
        a, b, c = map(int, input().split())
        if a:
            ans.append(bit.folded(b, c))
        else:
            bit.point_append(b, c)

    print('\n'.join(map(str, ans)))

if __name__ == "__main__":
    main()

Solution (Python):
class BIT():

    __slots__ = ["n", "data"]

    def __init__(self, length_or_list):
        if isinstance(length_or_list, int):
            self.n = length_or_list + 1
            self.data = [0] * self.n
        else:
            self.n = len(length_or_list) + 1
            self.data = [0] + length_or_list
            for i in range(1, self.n):
                if i + (i & -i) < self.n:
                    self.data[i + (i & -i)] += self.data[i]        

    def point_append(self, index, delta):
        index += 1
        while index < self.n:
            self.data[index] += delta
            index += index & -index
        
    def prefix_folded(self, end):
        res = 0
        while end > 0:
            res += self.data[end]
            end -= end & -end
        return res

    def folded(self, begin, end):
        ret = 0
        while begin < end:
            ret += self.data[end]
            end -= end & -end
        while end < begin:
            ret -= self.data[begin]
            begin -= begin & -begin
        return ret

def main():
    import sys
    input = sys.stdin.buffer.readline

    N, Q = map(int, input().split())
    bit = BIT(list(map(int, input().split())))
    ans = []
    for _ in range(Q):
        a, b, c = map(int, input().split())
        if a:
            ans.append(bit.folded(b, c))
        else:
            bit.point_append(b, c)

    print('\n'.join(map(str, ans)))

if __name__ == "__main__":
    main()

Solution (Python):


def lowbit(x):
	return x & (-x)

def update(n , c ,x , y):
	while x <= n:
		c[x] += y
		x += lowbit(x)

def query(c , x):
	ans = 0
	while x != 0:
		ans += c[x]
		x -= lowbit(x)
	return ans

def main():
	n , q = map(int , input().split())
	a_li = list(map(int , input().split()))
	a_li.insert(0,0)
	sum_li = [0 for _ in range(n + 1)]
	for i in range(1 , n + 1):
		sum_li[i] = sum_li[i - 1] + a_li[i]

	c = [0 for _ in range(n + 1)]
	for _ in range(q):
		t , l , r = map(int , input().split())
		if t == 1:
			print(query(c , r) - query(c , l) +  sum_li[r] - sum_li[l])
		else:
			update(n , c , l + 1 , r)

if __name__ == '__main__':
	main()

Solution (Python):
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))


class BIT():
    def __init__(self,init_value):
        self.n = len(init_value)
        self.tree = [0]*(self.n+1)
        for i in range(1,self.n+1):
            x = init_value[i-1]
            while i <= self.n:
                self.tree[i] += x
                i += i & (-i)
    def update(self,i,x):  
        while i <= self.n:
            self.tree[i] += x
            i += i & (-i)
        return
    def query(self,i):  
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & (-i)
        return res


N,Q = MI()
A = LI()
BIT = BIT(A)
for _ in range(Q):
    p,q,r = MI()
    if p == 0:
        BIT.update(q+1,r)
    else:
        print(BIT.query(r)-BIT.query(q))

Solution (Python):
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
a = list(map(int, input().split()))

class FenwickTree:
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 2)
  def sum(self, l, r):
    s = 0
    while l > 0:
      s -= self.data[l]
      l -= l & -l
    while r > 0:
      s += self.data[r]
      r -= r & -r
    return s
  def add(self, i, x):
    i += 1
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def lowerbound(self, s):
    x = 0
    y = 0
    for i in range(self.n.bit_length(), -1, -1):
      k = x + (1 << i)
      if k <= self.n and (y + self.data[k] < s):
        y += self.data[k]
        x += 1 << i
    return x + 1
fwk = FenwickTree(N)
for x in range(N): fwk.add(x, a[x])
for _ in range(Q):
  q, x, y = map(int, input().split())
  if q: print(fwk.sum(x, y))
  else: fwk.add(x, y)

Solution (Python):
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
a = list(map(int, input().split()))

class FenwickTree:
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 2)
  def sum(self, i):
    i += 1
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    i += 1
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def lowerbound(self, s):
    x = 0
    y = 0
    for i in range(self.n.bit_length(), -1, -1):
      k = x + (1 << i)
      if k <= self.n and (y + self.data[k] < s):
        y += self.data[k]
        x += 1 << i
    return x + 1
fwk = FenwickTree(N)
for x in range(N): fwk.add(x, a[x])
for _ in range(Q):
  q, x, y = map(int, input().split())
  if q: print(fwk.sum(y - 1) - fwk.sum(x - 1))
  else: fwk.add(x, y)

Solution (Python):
import sys
input = sys.stdin.readline

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def build(self, lis):
        self.value = lis
        for i, x in enumerate(lis):
            self.add(i+1, x)

    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 get_sum(self, i, j):
        return self.sum(j) - self.sum(i)


def main():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    
    bit = FenwickTree(n)
    bit.build(a)
    
    for i in range(q):
        a, b, c = map(int, input().split())
        if a == 0:
            bit.add(b+1, c)
        else:
            print(bit.get_sum(b, c))
    
    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def build(self, lis):
        self.value = lis
        for i, x in enumerate(lis):
            self.add(i+1, x)

    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 get_sum(self, i, j):
        return self.sum(j) - self.sum(i)


def main():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    
    bit = FenwickTree(n)
    bit.build(a)
    
    for i in range(q):
        a, b, c = map(int, input().split())
        if a == 0:
            bit.add(b+1, c)
        else:
            print(bit.get_sum(b, c))
    
    
if __name__ == "__main__":
    main()

Solution (Python):
class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def build(self, lis):
        self.value = lis
        for i, x in enumerate(lis):
            self.add(i+1, x)

    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 get_sum(self, i, j):
        return self.sum(j) - self.sum(i)


def main():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    
    bit = FenwickTree(n)
    bit.build(a)
    
    for i in range(q):
        a, b, c = map(int, input().split())
        if a == 0:
            bit.add(b+1, c)
        else:
            print(bit.get_sum(b, c))
    
    
if __name__ == "__main__":
    main()

Solution (Python):
class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def build(self, lis):
        self.value = lis
        for i, x in enumerate(lis):
            self.add(i+1, x)

    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 get_sum(self, i, j):
        return self.sum(j) - self.sum(i)


def main():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    
    bit = FenwickTree(n)
    bit.build(a)
    
    for i in range(q):
        query = list(map(int, input().split()))
        if query[0] == 0:
            bit.add(query[1]+1, query[2])
        else:
            print(bit.get_sum(query[1], query[2]))
    
    
if __name__ == "__main__":
    main()

Solution (Python):
class FenwickTree:
    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 get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    


def main():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    
    bit = FenwickTree(n)
    for i, x in enumerate(a):
        bit.add(i+1, x)
    
    for i in range(q):
        query = list(map(int, input().split()))
        if query[0] == 0:
            bit.add(query[1]+1, query[2])
        else:
            print(bit.get_sum(query[1], query[2]))
    
    
if __name__ == "__main__":
    main()

Solution (Python):
class FenwickTree:
    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 get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    


def main():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    
    bit = FenwickTree(n)
    for i, x in enumerate(a):
        bit.add(i+1, x)
    
    for i in range(q):
        query = list(map(int, input().split()))
        if query[0] == 0:
            bit.add(query[1]+1, query[2])
        else:
            print(bit.get_sum(query[1], query[2]))
    
    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
readline = sys.stdin.readline
      
class BIT:
    
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.p = 2**(n.bit_length() - 1)
        self.dep = n.bit_length()
    def get(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
    
    def bl(self, v):
        if v <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < v:
                s += k
                v -= self.tree[s+k]
            k //= 2
        return s + 1
  
N, Q = map(int, readline().split())

T = BIT(N+1)
A = [0] + list(map(int, readline().split()))

for i in range(N+1):
    T.add(i+1, A[i])

Ans = []
for _ in range(Q):
    t, a, b = map(int, readline().split())
    if t == 0:
        T.add(a+2, b)
    else:
        Ans.append(T.get(b+1) - T.get(a+1))

print('\n'.join(map(str, Ans)))

Solution (Python):
def main():
  def f(i,x):
    while i<=n:
      b[i]+=x
      i+=i&-i
  def g(i):
    s=0
    while i:
      s+=b[i]
      i-=i&-i
    return s
  (n,q,*w),a,*t=[[*map(int,t.split())]for t in open(0)]
  b=[0]*-~n
  *map(f,range(1,n+1),a),
  for q,l,r in t:
    if q:w+=g(r)-g(l),
    else:f(l+1,r)
  print(' '.join(map(str,w)))
main()

Solution (Python):
def main():
  def f(i,x):
    while i<=n:
      b[i]+=x
      i+=i&-i
  def g(i):
    s=0
    while i:
      s+=b[i]
      i-=i&-i
    return s
  (n,q,*w),a,*t=[map(int,t.split())for t in open(0)]
  b=[0]*-~n
  *map(f,range(1,n+1),a),
  for q,l,r in t:
    if q:w+=g(r)-g(l),
    else:f(l+1,r)
  print(' '.join(map(str,w)))
main()

Solution (Python):
def f(i,x):
  while i<=n:
    b[i]+=x
    i+=i&-i
def g(i):
  s=0
  while i:
    s+=b[i]
    i-=i&-i
  return s
(n,q),a,*t=[map(int,t.split())for t in open(0)]
b=[0]*-~n
*map(f,range(1,n+1),a),
for q,l,r in t:
  if q:print(g(r)-g(l))
  else:f(l+1,r)

Solution (Python):
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

N,Q=map(int,input().split())
*A,=map(int,input().split())

bit=Bit(N)
for i in range(1,N+1):
    bit.add(i,A[i-1])

from sys import stdin
abc=[list(map(int,stdin.readline().split()))for _ in range(Q)]

for a,b,c in abc:
    if a:print(bit.sum(c)-bit.sum(b))
    else:bit.add(b+1,c)

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.buffer.readline

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

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

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

        def lower_bound(self, w):
            if w <= 0:
                return 0
            x = 0
            k = 1 << (self.size.bit_length() - 1)
            while k:
                if x + k <= self.size and self.tree[x + k] < w:
                    w -= self.tree[x + k]
                    x += k
                k >>= 1
            return x + 1

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


if __name__ == '__main__':
    main()

Solution (Python):
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

N,Q=map(int,input().split())
*A,=map(int,input().split())

bit=Bit(N)
for i in range(1,N+1):
    bit.add(i,A[i-1])

abc=[list(map(int,input().split()))for _ in range(Q)]

for a,b,c in abc:
    if a:print(bit.sum(c)-bit.sum(b))
    else:bit.add(b+1,c)

Solution (Python):
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

N,Q=map(int,input().split())
*A,=map(int,input().split())

bit=Bit(N)
for i in range(1,N+1):
    bit.add(i,A[i-1])

abc=[list(map(int,input().split()))for _ in range(Q)]

for a,b,c in abc:
    if a:print(bit.sum(c)-bit.sum(b))
    else:bit.add(b+1,c)

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

    def query(self,idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    
    def update(self,idx,x):
        while idx <= self.num:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return

import sys

input = sys.stdin.readline

N,Q = map(int,input().split())
a = list(map(int,input().split()))
bit = BIT(N)

for i in range(N):
    bit.update(i+1,a[i])

for i in range(Q):
    q,l,r = map(int,input().split())
    if q == 0:
        bit.update(l+1,r)
    else:
        res = bit.query(r) - bit.query(l)
        print(res)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class BinaryIndexTree:
    def __init__(self, n):
        self.size = n
        self._container = [0] * (n + 1)
        self.depth = n.bit_length()

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

    def add(self, i, x):
        if i == 0:
            return
        while i <= self.size:
            self._container[i] += x
            i += i & (-i)

    def lower_bound(self, x):
        if x == 0:
            return 0

        s = 0
        idx = 0
        for i in range(self.depth, -1, -1):
            k = idx + (1 << i)
            if k <= self.size and s + self._container[k] < x:
                s += self._container[k]
                idx += 1 << i
        return idx + 1

    def __repr__(self):
        return str(self._container)


def main():
    N, Q = map(int, readline().split())
    a = list(map(int, readline().split()))
    bit = BinaryIndexTree(N + 1)

    for i, x in enumerate(a, 1):
        bit.add(i, x)

    for _ in range(Q):
        a, b, c = map(int, readline().split())
        if a == 0:
            b += 1
            bit.add(b, c)
        else:
            b += 1
            c += 1
            print(bit.sum(c - 1) - bit.sum(b - 1))


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline






def main():
    def segfunc(x, y):
        return x + y

    def init(init_val):
        for i in range(n):
            seg[i + num - 1] = init_val[i]

        for i in range(num - 2, -1, -1):
            seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k - 1) // 2
            seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])

    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = segfunc(res, seg[p])
            if q & 1 == 1:
                res = segfunc(res, seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

    N, Q = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    
    n = N
    ide_ele = 0
    num = 2 ** (n - 1).bit_length()
    seg = [ide_ele] * 2 * num

    init(A)

    for _ in range(Q):
        q, p, x = [int(x) for x in input().split()]
        if q == 0:
            A[p] += x
            update(p, A[p])
        else:
            print(query(p, x))





if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline






def main():
    def segfunc(x, y):
        return x + y

    def init(init_val):
        for i in range(n):
            seg[i + num - 1] = init_val[i]

        for i in range(num - 2, -1, -1):
            seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k - 1) // 2
            seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])

    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = segfunc(res, seg[p])
            if q & 1 == 1:
                res = segfunc(res, seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

    N, Q = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    
    n = N
    ide_ele = 0
    num = 2 ** (n - 1).bit_length()
    seg = [ide_ele] * 2 * num

    init(A)

    for _ in range(Q):
        q, p, x = [int(x) for x in input().split()]
        if q == 0:
            A[p] += x
            update(p, A[p])
        else:
            print(query(p, x))





if __name__ == '__main__':
    main()

Solution (Python):
class BinaryIndexedTree():
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, idx):
        res = 0
        while idx:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

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

import sys
input = sys.stdin.buffer.readline

N, Q = map(int, input().split())
A = tuple(map(int, input().split()))

bit = BinaryIndexedTree(N)
res = list()

for i, a in enumerate(A):
    bit.add(i + 1, a)

for _ in range(Q):
    q, x, y = map(int, input().split())
    if q == 0:
        bit.add(x + 1, y)
    else:
        res.append(bit.sum(y) - bit.sum(x))

print('\n'.join(map(str, res)))