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



























class SegmentTree:
    
    
    
    def __init__(self, size, f=lambda x,y : min(x, y), idele=float('inf')):
        self.size = 2**(size-1).bit_length()    
        self.idele = idele                      
        self.f = f                              
        self.dat = [self.idele]*(self.size*2)   


    def update(self, i, x):
        i += self.size  
        self.dat[i] = x
        while i > 0:    
            i >>= 1     
            
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def add(self, i, x):
        i += self.size  
        self.dat[i] += x
        while i > 0:    
            i >>= 1     
            
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, l, r):
        l += self.size  
        r += self.size  
        lres, rres = self.idele, self.idele 
        while l < r:    
            
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1
            
            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres) 
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res

    def init(self, a):
        for i, x in enumerate(a):
            
            self.dat[i + self.size] = x
        for i in range(self.size-1, -1, -1):
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

n, q = map(int, input().split())
a = list(map(int, input().split()))
sgt = SegmentTree(n, lambda x,y : x+y, 0)
sgt.init(a)
for _ in range(q):
    t, u, v = map(int, input().split())
    if t == 0:
        sgt.add(u, v)
    else:
        print(sgt.query(u, v))

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*A8ul{!K_BJEm?@{7xn?pm|6-nE3KA-?(cVNnbc{Y$~}j3&po
    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!EWj>5WFMt4=bvtLJ2Wdd
    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!EWj>5WFMt4=bvtLJ2Wdd
    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(Qe`}5PV1CA68VSh7w|`-b01TeFbklgdBSV7LM)O4$!~9brMLb!!N+h?CkC=Pasu@O;kFpL349x_yIR!v6xPtKzzreH3Poact*W>OWdeT8KE1Ad
    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${rgL2iRE5WGj?4|8b)jT3>?N)<}_ku(P|23B=UVhl-tUpuA&n(hTNJKh<OUFzlt{%z_;ZBCiaq!bdIj;BT&oOGrt5iCkal9cmJYYJ-a{Yn^KXPQ|eDN_auUWgL1QPut}wv`-E3?L~<O4yIFyHyxLH5JJ;Sisi6FvuA=c8EQEsYwbX1Iblxn}cW=jWCtAv&HLsid>8AYwWmb94|;>tSo13Ilifd>9hi$+v^)DkQGJf%n-YIy3W0NQ-tjfYT~Te(*dg;t`k@8pYV(|%~f1LXuG3V`6mib_!|V_1Mx(%b@QF>RB}B^PLA2$4HzgFiMs-Z^SHE!H4Gg?A1p3p>Y1ss(RM1S;X
    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%Wi`(5WFMt4|8b)jT3>?N)<}_BWVsi46N$di7_Po``R%Lq^U2Mnep!I*tJ
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
code = """




from libcpp.vector cimport vector
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 FenwickTree:
    cdef fenwick_tree[long long] *_thisptr
    def __cinit__(self, int n):
        self._thisptr = new fenwick_tree[long long](n)
    cpdef void add(self, int p, long long x):
        self._thisptr.add(p, x)
    cpdef long 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(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
  
import sys
from atcoder import FenwickTree

N,Q = list(map(int,input().split()))
A = list(map(int,input().split()))
fw = FenwickTree(N)
for i, a in enumerate(A):
    fw.add(i,a)

for i in range(Q):
    a,b,c = list(map(int,input().split()))
    if a==0:
        fw.add(b,c)
    else:
        print(fw.sum(b,c))

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


class BIT1():
    """
    Binary Indexed Tree (1-indexed)
    """
    def __init__(self, n, data=None):
        self.n = n
        self.bit = [0] * (self.n + 1)
        self.data = [0] * (self.n + 1)
        if data:
            self.build(data)

    def build(self, data):
        for i in range(self.n):
            self.bit[i + 1] = self.data[i + 1] = data[i]
        for i in range(1, self.n):
            j = i + (i & (-i))
            if j <= self.n:
                self.bit[j] += self.bit[i]

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

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


n, q = map(int, input().split())
a = list(map(int, input().split()))
bit = BIT1(n, a)
for _ in range(q):
    t, p, q = map(int, input().split())
    if t == 0:
        bit.add(p + 1, q)
    else:
        print(bit.sum(q) - bit.sum(p))

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


class BIT1():
    """
    Binary Indexed Tree (1-indexed)
    """
    def __init__(self, n, data=None):
        self.n = n
        self.bit = [0] * (self.n + 1)
        self.data = [0] * (self.n + 1)
        if data:
            self.build(data)

    def build(self, data):
        for i in range(self.n):
            self.bit[i + 1] = self.data[i + 1] = data[i]
        for i in range(1, self.n):
            j = i + (i & (-i))
            if j <= self.n:
                self.bit[j] += self.bit[i]

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

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


n, q = map(int, input().split())
a = list(map(int, input().split()))
bit = BIT1(n, a)
for _ in range(q):
    t, p, q = map(int, input().split())
    if t == 0:
        bit.add(p + 1, q)
    else:
        print(bit.sum(q) - bit.sum(p))

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


class BinaryIndexedTree:
    """一点加算、区間総和クエリをそれぞれO(logN)で答えるデータ構造。"""
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

    def build(self, array):
        """arrayを初期値とするBinaryIndexedTreeを構築する。O(N)"""
        for i, val in enumerate(array):
            self.bit[i + 1] = val
        for i in range(1, self.size):
            if i + (i & -i) > self.size:
                continue
            self.bit[i + (i & -i)] += self.bit[i]

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

    def add(self, i, val):
        """i番目の要素にvalを加算する。O(logN)"""
        i += 1
        while i <= self.size:
            self.bit[i] += val
            i += i & -i

    def sum(self, l, r):
        """区間[l, r)の和を求める。O(logN)"""
        return self._sum(r) - self._sum(l)

    def bisect_left(self, val):
        """区間[0, ind)の和がval以上になる最小のindを求める。O(logN)"""
        if val <= 0:
            return 0
        ind = 0
        k = 1 << self.size.bit_length()
        while k:
            if ind + k <= self.size and self.bit[ind + k] < val:
                val -= self.bit[ind + k]
                ind += k
            k >>= 1
        return ind + 1


n, q = map(int, input().split())
a = list(map(int, input().split()))
queries = [list(map(int, input().split())) for _ in range(q)]


bit = BinaryIndexedTree(n)
bit.build(a)
ans = []
for flag, l, r in queries:
    if flag:
        ans.append(bit.sum(l, r))
    else:
        bit.add(l, r)  

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