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):

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+1:
        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

ide_ele=0
n,q=map(int,input().split())
num=2**(n-1).bit_length()
seg=[ide_ele]*2*num
a=list(map(int,input().split()))
init(a)
ans=0
for i in range(q):
    x,l,r=map(int,input().split())
    if x==0:
        update(l,seg[l+num-1]+r)
    else:
        print(query(l,r))

Solution (Python):

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+1:
        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

ide_ele=0
n,q=map(int,input().split())
num=2**(n-1).bit_length()
seg=[ide_ele]*2*num
a=list(map(int,input().split()))
init(a)
ans=0
for i in range(q):
    x,l,r=map(int,input().split())
    if x==0:
        update(l,query(l,l+1)+r)
    else:
        print(query(l,r))

Solution (Python):
import sys
input=sys.stdin.readline
n,q=map(int, input().split())
*a,=map(int, input().split())
bit=[0]*(n+1)

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

def que(t):
    res=0
    while t:
        res+=bit[t]
        t-=t&(-t)
    return res

for i in range(n):
    add(i+1,a[i])


for _ in range(q):
    i,p,x=map(int, input().split())
    if i:
        ans=que(x)-que(p)
        print(ans)
    else:
        add(p+1,x)

Solution (Python):
import sys
input=sys.stdin.readline
n,q=map(int, input().split())
*a,=map(int, input().split())
bit=[0]*(n+1)

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

def que(t):
    res=0
    while t:
        res+=bit[t]
        t-=t&(-t)
    return res

for i in range(n):
    add(i+1,a[i])


for _ in range(q):
    i,p,x=map(int, input().split())
    if i:
        ans=que(x)-que(p)
        print(ans)
    else:
        add(p+1,x)

Solution (Python):
n,q=map(int, input().split())
*a,=map(int, input().split())
bit=[0]*(2*n+1)

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

def que(t):
    res=0
    while t:
        res+=bit[t]
        t-=t&(-t)
    return res

for i in range(n):
    add(i+1,a[i])


for _ in range(q):
    i,p,x=map(int, input().split())
    if i:
        ans=que(x)-que(p)
        print(ans)
    else:
        add(p+1,x)

Solution (Python):
class fenwick_tree:
    def __init__(self, n):
        self._n = n
        self.data = [0] * n
    
    def add(self, p: int, x: int):
        assert 0 <= p and p <= self._n
        p += 1
        while p <= self._n:
            self.data[p - 1] += x
            p += p & -p
    
    def sum(self, l: int, r: int) -> int:
        assert 0 <= l and l <= r and r <= self._n
        return self.__sum(r) - self.__sum(l)
    
    def __sum(self, r: int) -> int:
        s = 0
        while r > 0:
            s += self.data[r - 1]
            r -= r & -r
        return s





import sys









MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def Main():
    n, q = read_ints()
    a = read_int_list()
    fw = fenwick_tree(n)
    for i, x in enumerate(a):
        fw.add(i, x)
    for _ in range(q):
        query = read_int_list()
        if query[0] == 0:
            fw.add(query[1], query[2])
        else:
            print(fw.sum(query[1], query[2]))

if __name__ == '__main__':
    Main()

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

query=[]
for i in range(q):
    query.append(input())
ide_ele = 0

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

class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        
        
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1
    def query(self, l, r): 
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

al = [a[i] for i in range(n)]
seg = SegTree(al, segfunc, ide_ele)

for q in query:
    que,a,b=q.split()

    if que == "0":
        now=seg.query(int(a),int(a)+1)
        seg.update(int(a),now+int(b))
    else:
        ret=seg.query(int(a),int(b))
        print(ret)

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${rg(Qbk;6n!V*A8xX2!mLJ;Em?@{EB5AmfVRNRYOAH7`}?&PrB3@)&N<wB?zw
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${@p+is&U5Pe7DA4Xbjg}0;ysg)|!>{s+H$^
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${@pT~FgM5PYxH|1i?&P;
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${rg!EVAZ482$CKlrlIjDU)?NmB*;5yqiy(l%O1AWaJU`
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${rg!EVAZ482$CKlrlIjDT8clO_cF5yqiy(l%O1AWaJU`
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${rgL2kk@5WGjqANJCc6oZ1)N>v0s^nlb;A3
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${rg!ES>v480@q558<AYg&P{NfT=KBV7+b0z^xbHYBwB`
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${rgL2iRE5WFMthrP7HjT3>?N)<}_ktheS4Xo<ei7_PoeeIYAr-@HyX4svbbz}4a*pKbBS|2M@Nhu^SJRG&La5R-_MVd5TB(Y}e-g4A8z7>{rm7z|E$~I}jxM)CX)$TrWcZxmm33R;sO=Sd>Zc&zL0`A<XngW9@<N-c+C<PRg$e-GgQ@4!FFgA|a!24$jwGq|
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${rgL2iRE5WFMthrP7HjT3>?N)<}_ku(Re4Xo<ei7_PoeeIYAr>Re7X4svbbz}4a*thMpS|2M@Nhu^SJRG&La5R-_MVd5TB(Y}e-g4A8z7>{rm7z|E$~I}jxM)CX)$ZPMcZxmm33R;sO=Sd>Zc&zL0`A<XngW9@<N-c+C<PRg$e-GgQ@4!FFgA|a!0USnwGq|V%=l^yUZBWf=`<^+38WErFbde@Yt+c0;ym*%kY3GP?o9?a2%9aa$P(Y-9+q3UM0Wf)!ZWNe$^!b~5X%2Ed=UH{9pMA=s8{a``-X9^)!Zu@td9a$J_H{+h0}a>Q(6iGg)vReXuCU8jW(_-s%iI`B4voj
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${rgL2iRE5WFMthrP7HjT3>?N)<}_ku(Re4Xo<ei7_PoeeIYAr>Re7X4svbbz}4a*thMpS|2M@Nhu^SJRG&La5R-_MVd5TB(Y}e-g4A8z7>{rm7z|E$~I}jxM)CX)$ZPMcZxmm33R;sO=Sd>Zc&zL0`A<XngW9@<N-c+C<PRg$e-GgQ@4!FFgA|a!0USnwGq|V%=l^yUZBWf=`<^+38WErFbde@Yt+c0;ym*%kY3GP?o9?a2%9aa$P(Y-9+q3UM0Wf)!ZWNe$^!b~5X%2Ed=UH{9pMA=s8{a``-X9^)!Zu@td9a$J_H{+h0}a>Q(6iGg)vReXuCU8jW(_-s%iI`B4voj
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${sL!EWL(5Qgtayu*lURVXHDwR@=0a@{B3)<u=ECy9k)yY>Xyx8HFHOIn&sqWOOR{%0n4piQEVj7@8>($$@;aif;Y>Ev
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
code = r"""




from libcpp cimport bool
from libcpp.vector cimport vector
cdef extern from "/opt/atcoder-stl/atcoder/dsu.hpp" namespace "atcoder":
    cpdef cppclass dsu:
        dsu(int n)
        int merge(int a, int b)
        bool same(int a, int b)
        int leader(int a)
        int size(int a)
        vector[vector[int]] groups()
cdef class dsu_:
    cdef dsu *ptr
    def __cinit__(self, int n): self.ptr = new dsu(n)
    def __dealloc__(self): del self.ptr
    cpdef int merge(self,a,b): return self.ptr.merge(a,b)
    cpdef bool same(self,a,b): return self.ptr.same(a,b)
    cpdef int leader(self,a): return self.ptr.leader(a)
    cpdef int size(self,a): return self.ptr.size(a)
    cpdef vector[vector[int]] groups(self): return self.ptr.groups()

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)
cdef class fenwick_tree_:
    cdef fenwick_tree[long] *ptr
    def __cinit__(self, int n): self.ptr = new fenwick_tree[long](n)  
    def __dealloc__(self): del self.ptr
    cpdef void add(self, int p, long x): self.ptr.add(p, x)
    cpdef long sum(self, int l, int r): return self.ptr.sum(l, r)
"""
import os
try:
    from atcoder import *
except:
    open('atcoder.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')

N,Q=map(int,input().split())
A=list(map(int,input().split()))
QRS=[list(map(int,input().split())) for i in range(Q)]
f=fenwick_tree_(N)
for i in range(N):
    f.add(i,A[i])
a=[]
for q,r,s in QRS:
    if q==0:
        f.add(r,s)
    else:
        a.append(f.sum(r,s))
print(*a,sep='\n')

Solution (Python):
code = r"""


from libcpp cimport *

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

import sys
input = sys.stdin.buffer.readline

N, Q = map(int, input().split())
cdef fenwick_tree[long] bit 
bit = fenwick_tree[long](N)

A = list(map(int, input().split()))
for i, a in enumerate(A):
    bit.add(i, a)

for _ in range(Q):
    t, u, v = map(int, input().split())
    if t == 0:
        bit.add(u, v)
    else:
        print(bit.sum(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):
class BinaryIndexedTree():
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        self.depth = self.size.bit_length()
 
    def initialize(self, seq):
        for i, x in enumerate(seq[1:], 1):
            self.tree[i] += x
            j = i + (i & (-i))
            if j < self.size:
                self.tree[j] += self.tree[i]
 
    def __repr__(self):
        return self.tree.__repr__()
 
    def get_sum(self, i):
        s = 0
        while i:
            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 find_kth_element(self, k):
        x, sx = 0, 0
        dx = (1 << self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= self.size:
                continue
            y = x + dx
            sy = sx + self.tree[y]
            if sy < k:
                x, sx = y, sy
        return x + 1


n,q = map(int,input().split())
a = list(map(int,input().split()))
bit = BinaryIndexedTree(n+2)
for i in range(n):
    bit.add(i+1,a[i])
for i in range(q):
    w,b,c = map(int,input().split())
    if w:
        t = bit.get_sum(c)-bit.get_sum(b)
        print(t)
    else:
        bit.add(b+1,c)

Solution (Python):
library = """




from libcpp cimport bool
cdef extern from "/opt/atcoder-stl/atcoder/dsu.hpp" namespace "atcoder":
    cdef cppclass dsu:
        dsu(int n)
        int merge(int a, int b)
        bool same(int a, int b)
        int leader(int a)
        int size(int a)
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)
cdef class DSU:
    cdef dsu *_thisptr
    def __cinit__(self, int n):
        self._thisptr = new dsu(n)
    def __dealloc__(self):
        del self._thisptr
    cpdef int merge(self, int a, int b):
        return self._thisptr.merge(a, b)
    cpdef bool same(self, int a, int b):
        return self._thisptr.same(a, b)
    cpdef int leader(self, int a):
        return self._thisptr.leader(a)
    cpdef int size(self, int a):
        return self._thisptr.size(a)
cdef class BIT:
    cdef fenwick_tree[long] *_thisptr
    def __cinit__(self, int n):
        self._thisptr = new fenwick_tree[long](n)  
    def __dealloc__(self):
        del self._thisptr
    cpdef void add(self, int p, long x):
        self._thisptr.add(p, x)
    cpdef long sum(self, int l, int r):
        return self._thisptr.sum(l, r)
"""
import os,sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('atcoder.pyx','w').write(library)
    os.system('cythonize -i -3 -b atcoder.pyx')



import sys
import atcoder
input = sys.stdin.buffer.readline
n, q = map(int, input().split())
bit = atcoder.BIT(n)
*map(bit.add, range(n), map(int, input().split())),
res = []
for i in range(q):
    t, u, v = map(int, input().split())
    if t: res.append(bit.sum(u, v))
    else: bit.add(u, v)
print('\n'.join(map(str, res)))

Solution (Python):
class segtree:
    def __init__(self, bin_level):
        self.bl = bin_level
        self.st = [[0 for __ in range(1<<_)] for _ in range(bin_level+1)]
    
    def st_make(self, n, arr):
        for j in range(n):
            tmp = j
            for i in range(self.bl, -1, -1):
                self.st[i][tmp] += arr[j]
                tmp >>= 1
    
    def st_add(self, i, p):
        tmp = i
        for i in range(self.bl, -1, -1):
            self.st[i][tmp] += p
            tmp >>= 1
    
    def st_sum(self, x):
        if x < 0:
            return 0
        S = 0
        pnt = 0
        b = 1 << (self.bl)
        for i in range(self.bl+1):
            pnt <<= 1
            if x >= b:
                S += self.st[i][pnt]
                pnt += 1
                x -= b
            b >>= 1
        return S

N, Q = map(int, input().split())
def powlimit(n):
    y = 1
    cnt = 0
    while y < n:
        y *= 2
        cnt += 1
    return cnt
st = segtree(powlimit(N))
st.st_make(N, list(map(int, input().split())))
for i in range(Q):
    t, l, r = map(int, input().split())
    if t:
        print(st.st_sum(r) - st.st_sum(l))
    else:
        st.st_add(l, r)

Solution (Python):
class BIT():

    __slots__ = ["n", "data"]

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

    def add(self, i, a):
        i += 1
        while i < self.n:
            self.data[i] += a
            i += i & -i
        
    def acc(self, i):
        res = 0
        while i > 0:
            res += self.data[i]
            i -= i & -i
        return res
    
    def fold(self, l, r):
        res = 0
        while l < r:
            res += self.data[r]
            r -= r & -r
        while r < l:
            res -= self.data[l]
            l -= l & -l
        return res

import sys
input = sys.stdin.buffer.readline
n, q = map(int, input().split())
A = list(map(int, input().split()))
bit = BIT(A)
for _ in range(q):
    t, p, x = map(int, input().split())
    if t == 0:
        bit.add(p, x)
    else:
        print(bit.fold(p, x))

Solution (Python):
class BIT():

    __slots__ = ["n", "data"]

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

    def add(self, i, a):
        i += 1
        while i < self.n:
            self.data[i] += a
            i += i & -i
        
    def acc(self, i):
        res = 0
        while i > 0:
            res += self.data[i]
            i -= i & -i
        return res
    
    def fold(self, l, r):
        return self.acc(r) - self.acc(l)

import sys
input = sys.stdin.buffer.readline
n, q = map(int, input().split())
A = list(map(int, input().split()))
bit = BIT(A)
for _ in range(q):
    t, p, x = map(int, input().split())
    if t == 0:
        bit.add(p, x)
    else:
        print(bit.fold(p, x))

Solution (Python):
class BIT():

    __slots__ = ["n", "data"]

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

    def add(self, i, a):
        i += 1
        while i < self.n:
            self.data[i] += a
            i += i & -i
        
    def acc(self, i):
        res = 0
        while i > 0:
            res += self.data[i]
            i -= i & -i
        return res
    
    def fold(self, l, r):
        return self.acc(r) - self.acc(l)

import sys
input = sys.stdin.buffer.readline
n, q = map(int, input().split())
A = list(map(int, input().split()))
bit = BIT(A)
for _ in range(q):
    t, p, x = map(int, input().split())
    if t == 0:
        bit.add(p, x)
    else:
        print(bit.fold(p, x))

Solution (Python):

import sys
def input(): return sys.stdin.readline().rstrip()


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 main():
    n,q=map(int, input().split())
    A=list(map(int, input().split()))
    bi=Bit(n)
    for i in range(n):
        bi.add(i+1,A[i])
    for _ in range(q):
        q1,q2,q3=map(int, input().split())
        if q1==0:
            bi.add(q2+1,q3)
        else:
            print(bi.sum(q3)-bi.sum(q2))
        
    



if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


class BinaryIndexTree:  
    def __init__(self, N):
        """
        INPUT
        N [int] -> 全部0で初期化
        N [list] -> そのまま初期化
        """
        if isinstance(N, int):
            self.N = N
            self.depth = N.bit_length()
            self.tree = [0] * (N + 1)
            self.elem = [0] * (N + 1)
        elif isinstance(N, list):
            self.N = len(N)
            self.depth = self.N.bit_length()
            self.tree = [0] + N
            self.elem = [0] + N
            self._init()
        else:
            raise "INVALID INPUT: input must be int or list"

    def _init(self):
        size = self.N
        for i in range(1, self.N):
            if i + (i & -i) > size:
                continue
            self.tree[i + (i & -i)] += self.tree[i]

    def show(self):
        print(*self.elem)

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

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

    def lower_bound(self, val):
        if val <= 0:
            return 0
        i = 0
        k = 1 << self.depth
        while k:
            if i + k <= self.N and self.tree[i + k] < val:
                val -= self.tree[i + k]
                i += k
            k >>= 1
        return i + 1


N, Q = map(int, input().split())
A = list(map(int, input().split()))
bit = BinaryIndexTree(A)

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

Solution (Python):
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
mod = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class SegmentTree(object):
	
	def __init__(self, N):
		self.N = N
		self.N0 = 2 ** (N - 1).bit_length()
		self.initVal = 0
		self.data = [self.initVal] * (2 * self.N0)

	
	def calc(self, a, b):
		return a + b

	
	def initialize(self, A):
		for i in range(self.N):
			self.data[self.N0 - 1 + i] = A[i]
		for i in range(self.N0 - 2, -1, -1):
			self.data[i] = self.calc(self.data[2 * i + 1], self.data[2 * i + 2])

	
	def update(self, k, x):
		k += self.N0 - 1
		self.data[k] = x
		while k > 0:
			k = (k - 1) // 2
			self.data[k] = self.calc(self.data[2 * k + 1], self.data[2 * k + 2])

	
	def pointQuery(self, k):
		return self.data[k + self.N0 - 1]

	
	def add(self, k, x):
		k += self.N0 - 1
		self.data[k] += x
		while k > 0:
			k = (k - 1) // 2
			self.data[k] = self.calc(self.data[2 * k + 1], self.data[2 * k + 2])

	
	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				m = self.calc(m, self.data[R - 1])
			if L & 1:
				m = self.calc(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1

		return m

def main():
	N, Q = getlist()
	A = getlist()
	Seg = SegmentTree(N)
	Seg.initialize(A)
	for i in range(Q):
		q, a, b = getlist()
		if q == 0:
			Seg.add(a, b)
		else:
			res = Seg.query(a, b - 1)
			print(res)

if __name__ == '__main__':
	main()

Solution (Python):
class Binary_Indexed_Tree:
    def __init__(self, n):
        """
        :param n: 最大の要素数
        """
        self.n = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length() - 1

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1)) - 1
        return s

    def built(self, array):
        """ array を初期値とするBITを構築 """
        for i, a in enumerate(array):
            self.add(i, a)

    def add(self, i, x):
        """ i 番目の要素に x を足す """
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

    def get(self, i, j):
        """ 部分区間和 [i, j) """
        if i == 0:
            return self.sum(j)
        return self.sum(j) - self.sum(i)

    def lower_bound(self, x, equal=False):
        """ (a0+a1+...+ai < x となる最大の i, その時の a0+a1+...+ai )
             a0+a1+...+ai <= x としたい場合は equal = True
             二分探索であるため、ai>=0 を満たす必要がある"""
        sum_ = 0
        pos = -1  
        if equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] <= x:  
                    sum_ += self.tree[k]
                    pos += 1 << i
        else:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] < x:  
                    sum_ += self.tree[k]
                    pos += 1 << i

        return pos, sum_

    def __getitem__(self, i):
        """ [a0, a1, a2, ...] """
        return self.get(i, i + 1)

    def __iter__(self):
        """ [a0, a1, a2, ...] """
        for i in range(self.n):
            yield self.get(i, i + 1)

    def __str__(self):
        text1 = " ".join(["element:            "] + list(map(str, self)))
        text2 = " ".join(["cumsum(1-indexed):  "] + list(str(self.sum(i)) for i in range(1, self.n + 1)))
        return "\n".join((text1, text2))


import sys
input = sys.stdin.readline
n, q = map(int, input().split())
a = list(map(int, input().split()))
b = Binary_Indexed_Tree(n)
b.built(a)
for i in range(q):
    q, x, y = map(int, input().split())
    if q:
        print(b.get(x, y))
    else:
        b.add(x, y)

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 = list(map(int, input().split()))
B = BIT(N)
i = 0
while a:
  B.add(N-i, a.pop())
  i += 1
while Q:
  Q -= 1
  s, t, u = map(int, input().split())
  if s == 0:
    p = t + 1 
    x = u
    B.add(p, x)
  else:
    l = t + 1
    r = u + 1
    print(B.sum(r-1) - B.sum(l-1))

Solution (Python):
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(self.n+1) 
 
    def init(self, init_val):
        for i, v in enumerate(init_val):
            self.add(i, v)
 
    def add(self, i, x):
        
        i += 1 
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)
 
    def sum(self, i, j):
        
        
        return self._sum(j) - self._sum(i)
 
    def _sum(self, i):
        
        
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & (-i)
        return res
 
    def lower_bound(self, x):
        s = 0
        pos = 0
        depth = self.n.bit_length()
        v = 1 << depth
        for i in range(depth, -1, -1):
            k = pos + v
            if k <= self.n and s + self.bit[k] < x:
                    s += self.bit[k]
                    pos += v
            v >>= 1
        return pos

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

bit = BIT(n)
bit.init(A)

for _ in range(q):
  i, j, k = map(int, input().split())
  if i == 0:
    bit.add(j, k)
  else:
    print(bit.sum(j, k))

Solution (Python):
import math


class BinaryIndexedTree():
    def __init__(self, N):
        self.N = N
        self.arr = [0] * (N+1)

    def query(self, i):
        ret = 0
        i += 1
        while i:
            ret += self.arr[i]
            lsb = i & (-i)
            i -= lsb
        return ret

    def add(self, i, v):
        i += 1
        while i < self.N+1:
            lsb = i & (-i)
            self.arr[i] += v
            i += lsb

    def search(self, x):
        pos = 0
        cur = 0
        idx = 2 ** int(math.log(self.N, 2))
        while idx >= 1:
            if pos + idx <= self.N and cur + self.arr[pos+idx] < x:
                cur += self.arr[pos+idx]
                pos += idx
            idx //= 2
        return pos


def main():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    bit = BinaryIndexedTree(N)
    for i, a in enumerate(A):
        bit.add(i, a)
    for _ in range(Q):
        qtype, a, b = map(int, input().split())
        if qtype == 0:
            bit.add(a, b)
        else:
            ans = bit.query(b-1) - bit.query(a-1)
            print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
S=sys.stdin.readlines()
def Binit(B,siz):
  while len(B)<siz+1:
    B.append(0)
  while len(B)>siz+1:
    del B[-1]
  for i in range(siz+1):
    B[i]=0
  B.append(siz)

def Badd(B,a,x):
  z=a
  while z<=B[-1]:
    B[z]+=x
    z+=(z&(-z))

def Bsum(B,a):
  r=0
  z=a
  while z>0:
    r+=B[z]
    z-=(z&(-z))
  return r

def Bssum(B,a,b):
  return Bsum(B,max(a,b))-Bsum(B,min(a,b)-1)

BIT=[]
N,Q=map(int,S[0].split())
Binit(BIT,N+1)
A=list(map(int,S[1].split()))
for i in range(N):
  Badd(BIT,i+1,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(Bssum(BIT,b+1,c))
  else:
    Badd(BIT,b+1,c)