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 FenwickTree: 
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 1)
    self.el = [0] * (n + 1)
  
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  
  def add(self, i, x):
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i

  def get(self, i, j = None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i - 1)
    
import sys
readline = sys.stdin.readline

N,Q = map(int,readline().split())
A = list(map(int,readline().split()))

FT = FenwickTree(N)

for i in range(len(A)):
  FT.add(i + 1, A[i])
  
for i in range(Q):
  query = list(map(int,readline().split()))
  if query[0] == 0:
    FT.add(query[1] + 1, query[2])
  else:
    print(FT.get(query[1] + 1, query[2]))

Solution (Python):
def main():
    N, Q = map( int, input().split())
    A = list( map( int, input().split()))
    bit = [0]*N
    def add(bit,a,w):
        x = a
        while x <= N:
            bit[x-1] += w
            x += x&(-x)

    def sums(bit,a):
        x = a
        S = 0
        while x > 0:
            S += bit[x-1]
            x -= x&(-x)
        return S

    for i, a in enumerate(A):
        add(bit,i+1,a)
    Q = [ tuple( map( int, input().split())) for _ in range(Q)]
    ANS = []
    for q,p,x in Q:
        if q == 0:
            add(bit,p+1,x)
        else:
            ANS.append( sums(bit,x)-sums(bit,p))
    print( "\n".join( map( str, ANS)))
if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N, Q = map( int, input().split())
    A = list( map( int, input().split()))
    bit = [0]*N
    def add(bit,a,w):
        x = a
        while x <= N:
            bit[x-1] += w
            x += x&(-x)

    def sums(bit,a):
        x = a
        S = 0
        while x > 0:
            S += bit[x-1]
            x -= x&(-x)
        return S

    for i, a in enumerate(A):
        add(bit,i+1,a)
    Q = [ tuple( map( int, input().split())) for _ in range(Q)]
    ANS = []
    for q,p,x in Q:
        if q == 0:
            add(bit,p+1,x)
        else:
            ANS.append( sums(bit,x)-sums(bit,p))
    print( "\n".join( map( str, ANS)))
if __name__ == '__main__':
    main()

Solution (Python):
class fenwick_tree(object):
    def __init__(self, n):
        self.n = n
        self.data = [0] * n

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

    def add(self, p, x):
        """ a[p] += xを行う"""
        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, r):
        """a[l] + a[l+1] + .. + a[r-1]を返す"""
        assert 0 <= l and l <= r and r <= self.n
        return self.__sum(r) - self.__sum(l)


if __name__ == "__main__":
    import sys
    input = sys.stdin.buffer.readline
    sys.setrecursionlimit(10 ** 7)
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))

    fw = fenwick_tree(N)
    for i, a in enumerate(A):
        fw.add(i, a)

    for _ in range(Q):
        t, u, v = map(int, input().split())
        if t == 0:
            fw.add(u, v)
        else:
            print(fw.sum(u, v))

Solution (Python):
class Binary_Indexed_Tree_Exception(Exception):
    pass

class Binary_Indexed_Tree():
    def __init__(self,L,calc,unit,inv):
        """calcを演算とするN項のBinary Indexed Treeを作成

        calc:演算(2変数関数,群)
        unit:群calcの単位元(xe=ex=xを満たすe)
        inv:群calcの逆元(1変数関数)
        """
        self.calc=calc
        self.unit=unit
        self.inv=inv

        N=len(L)
        d=max(1,(N-1).bit_length())
        k=2**d

        X=[None]+[unit]*k

        self.num=k
        self.depth=d

        if L:
            for i in range(len(L)):
                p=i+1
                while p<=k:
                    X[p]=calc(X[p],L[i])
                    p+=p&(-p)
        self.data=X

    def index(self,k,index=1):
        """第k要素の値を出力する.

        k:数列の要素
        index:先頭の要素の番号
        """

        p=k+(1-index)
        return self.sub_array(p,p)

    def add(self,k,x,index=1,right=False):
        """第k要素にxを左から加え,更新を行う.

        k:数列の要素
        x:更新後の値
        index:先頭の要素の番号
        right:「左から」が「右から」になる
        """
        p=k+(1-index)
        while p<=self.num:
            if right==False:
                
                self.data[p]=self.calc(x,self.data[p])
            else:
                
                self.data[p]=self.cal(self.data[p],x)
            p+=p&(-p)

    def update(self,k,x,index=1,right=False):
        """第k要素をxに変え,更新を行う.

        k:数列の要素
        x:更新後の値
        """

        a=self.index(k,index)
        if right==False:
            
            y=self.calc(x,self.inv(a))
        else:
            
            y=self.calc(self.inv(a),x)

        self.add(k,y,index,right)

    def product(self,From,To,index=1):
        """第From要素から第To要素までの総和を求める.

        From:始まり
        To:終わり
        index:先頭の要素の番号
        """
        alpha=max(1,From+(1-index))
        beta=min(self.num,To+(1-index))
        return self.calc(self.inv(self.__section(alpha-1)),self.__section(beta))

    def __section(self,To):
        S=self.unit
        x=To
        while x>0:
            S=self.calc(self.data[x],S)
            x-=x&(-x)
        return S

    def all_product(self):
        return self.data[-1]


N,Q=map(int,input().split())
A=list(map(int,input().split()))
B=Binary_Indexed_Tree(A,lambda x,y:x+y,0,lambda x:-x)

X=[]
for _ in range(Q):
    t,u,v=map(int,input().split())
    if t==0:
        B.add(u,v,0)
    else:
        X.append(B.product(u,v-1,0))
print("\n".join(map(str,X)))

Solution (Python):
import sys

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


def main():
    input = sys.stdin.readline
    n, q = map(int, input().split())
    fw = Fenwick_Tree(n)
    for i, a in enumerate(map(int, input().split())): fw.add(i, a)
    A = list(map(int, sys.stdin.read().split()))
    for i in range(0, 3 * q, 3):
        t, a, b = A[i:i+3]
        if t == 0:
            fw.add(a, b)
        else:
            print(fw.sum(a, b))

if __name__ == "__main__":
    main()

Solution (Python):
import sys

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


def main():
    input = sys.stdin.readline
    n, q = map(int, input().split())
    fw = Fenwick_Tree(n)
    for i, a in enumerate(map(int, input().split())): fw.add(i, a)
    for _ in range(q):
        t, a, b = map(int, input().split())
        if t == 0:
            fw.add(a, b)
        else:
            print(fw.sum(a, b))

if __name__ == "__main__":
    main()

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


def main():
    n, q = map(int, input().split())
    fw = Fenwick_Tree(n)
    for i, a in enumerate(map(int, input().split())): fw.add(i, a)
    for _ in range(q):
        t, a, b = map(int, input().split())
        if t == 0:
            fw.add(a, b)
        else:
            print(fw.sum(a, b))

if __name__ == "__main__":
    main()

Solution (Python):
class fenwick_tree():
    def __init__(self, n:int, mod:int = 0):
        self.__mod = mod
        self.__n = n
        self.__data = [0] * self.__n

    def add(self, p:int, x:int):
        assert (0 <= p) & (p < self.__n)
        if(self.__mod == 0):
            self.__add_mod0(p,x)
        else:
            self.__add_mod(p,x)

    def __add_mod0(self, p:int, x:int):
        p+=1
        while( p<= self.__n):
            self.__data[p-1] += x
            p += p & -p

    def __add_mod(self, p:int, x:int):
        p+=1
        while( p<= self.__n):
            self.__data[p-1] += x
            self.__data[p-1] %= self.__mod
            p += p & -p

    def sum(self, l:int, r:int):
        assert (0 <= l) & (l <= r) & (r <= self.__n)
        if(self.__mod == 0):
            return self.__sum_mod0(r) - self.__sum_mod0(l)
        else:
            return self.__sum_mod(r) - self.__sum_mod(l)

    def __sum_mod0(self, r:int):
        s = 0
        while(r > 0):
            s += self.__data[r-1]
            r -= r & -r
        return s

    def __sum_mod(self, r:int):
        s = 0
        while(r > 0):
            s += self.__data[r-1]
            s %= self.__mod
            r -= r & -r
        return s

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,q = map(int,readline().split())
a = list(map(int,readline().split()))
query = list(map(int,read().split()))

ft = fenwick_tree(n,mod=10**18)
ans = []

for i,ai in enumerate(a):
    ft.add(i,ai)

i = 0
for _ in range(q):
    if(query[i]==0):
        p,x = query[i+1:i+3]
        ft.add(p,x)
    else:
        l,r = query[i+1:i+3]
        ans.append(ft.sum(l,r))
    i += 3

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

Solution (Python):
class fenwick_tree():
    def __init__(self, n:int, mod:int = 0):
        self.__mod = mod
        self.__n = n
        self.__data = [0] * self.__n

    def add(self, p:int, x:int):
        assert (0 <= p) & (p < self.__n)
        if(self.__mod == 0):
            self.__add_mod0(p,x)
        else:
            self.__add_mod(p,x)

    def __add_mod0(self, p:int, x:int):
        p+=1
        while( p<= self.__n):
            self.__data[p-1] += x
            p += p & -p

    def __add_mod(self, p:int, x:int):
        p+=1
        while( p<= self.__n):
            self.__data[p-1] += x
            self.__data[p-1] %= self.__mod
            p += p & -p

    def sum(self, l:int, r:int):
        assert (0 <= l) & (l <= r) & (r <= self.__n)
        if(self.__mod == 0):
            return self.__sum_mod0(r) - self.__sum_mod0(l)
        else:
            return self.__sum_mod(r) - self.__sum_mod(l)

    def __sum_mod0(self, r:int):
        s = 0
        while(r > 0):
            s += self.__data[r-1]
            r -= r & -r
        return s

    def __sum_mod(self, r:int):
        s = 0
        while(r > 0):
            s += self.__data[r-1]
            s %= self.__mod
            r -= r & -r
        return s

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,q = map(int,readline().split())
a = list(map(int,readline().split()))
query = list(map(int,read().split()))

ft = fenwick_tree(n)
ans = []

for i,ai in enumerate(a):
    ft.add(i,ai)

i = 0
for _ in range(q):
    if(query[i]==0):
        p,x = query[i+1:i+3]
        ft.add(p,x)
    else:
        l,r = query[i+1:i+3]
        ans.append(ft.sum(l,r))
    i += 3

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

Solution (Python):
class BIT:
    """
    Binary Index Tree
    

    add :L[i]+=x
    sum: sum(L[:l])
    range_sum : sum(L[l:r])

    
    """

    def __init__(self, N, init_val=0):
        self.init_val = init_val
        self.size = N
        self.L = [init_val]*(N+1)

    def sum(self, r):
        """
        sum[,r)
        calc sum from L[0] to L[r-1]
        """
        ret = self.init_val
        while r > 0:
            ret += self.L[r]
            r -= r & (-r)

        return ret

    def range_sum(self, l, r):
        
        """
        idx周りが怪しい?
        sum[l,r)
        calc sum from L[l] to L[r-1]
        """
        return self.sum(r-1)-self.sum(l-1)

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

    def bisect(self,k:float)->int:
        """ binary search on BIT
        get index x s.t self.sum(,)>=k

        RETURN:
            res:index of x
        """
        k+=1 

        res=0
        N=1
        while N<self.size:
            N*=2

        i=N//2
        while i>0:
            if(res+i<self.size and self.L[res+i]<k): 
                k-=self.L[res+i]
                res+=i
            
            i//=2
        return res+1

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

B=BIT(N)
A=list(map(int,input().split()))
for i in range(N):
    B.add(i+1,A[i])

for _ in range(Q):
    v,l,r = map(int,input().split())
    if v==0:
        B.add(l+1,r)
    else:
        print(B.range_sum(l+1,r+1))

Solution (Python):
def getsum(BITTree, i): 
    s = 0
    i += 1
    while i > 0: 
        s += BITTree[i] 
        i -= i & (-i) 
    return s 
  
def updatebit(BITTree , n , i ,v): 
    i += 1
    while i <= n: 
        BITTree[i] += v 
        i += i & (-i) 

def construct(arr, n): 
    BITTree = [0]*(n+1) 
    for i in range(n): 
        updatebit(BITTree, n, i, arr[i]) 
    return BITTree

def main():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    BITTree = construct(a, len(a))
    for _ in range(q):
        i, j, k = map(int, input().split())
        if i:
            print(getsum(BITTree, k - 1) - getsum(BITTree, j - 1))
        else:
            updatebit(BITTree, len(a), j, k)
    
    
    
    
    
    
    

if __name__ == "__main__":
    main()

Solution (Python):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

class BIT:
    def __init__(self, n):
        self.n = n
        self.nums = [0] * (n+1)
        
    def add(self, i, x):
        n, nums = self.n, self.nums
        i += 1
        while i <= n:
            nums[i] += x
            i += i & -i
    
    def sum(self, i):
        nums = self.nums
        s = 0
        i += 1
        while i:
            s += nums[i]
            i -= i & -i
        return s

N, Q = rl()
bit = BIT(N)
A = rl()
for i, a in enumerate(A):
    bit.add(i, a)
for i in range(Q):
    q = rl()
    if q[0] == 0:
        bit.add(q[1], q[2])
    else:
        print(bit.sum(q[2]-1) - bit.sum(q[1]-1))

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

def solve():
    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def setInit(As):
        for iB, A in enumerate(As, 1):
            data[iB] = A
        for iB in range(1, numPow2):
            i = iB + (iB & -iB)
            data[i] += data[iB]
    def addValue(iA, A):
        iB = iA + 1
        while iB <= numPow2:
            data[iB] += A
            iB += iB & -iB
    def getSum(iA):
        iB = iA + 1
        ans = 0
        while iB > 0:
            ans += data[iB]
            iB -= iB & -iB
        return ans
    def getRangeSum(iFr, iTo):
        return getSum(iTo) - getSum(iFr-1)


    N, Q = map(int, input().split())
    As = list(map(int, input().split()))

    data, numPow2 = makeBIT(N)
    setInit(As)

    anss = []
    for _ in range(Q):
        t, i, j = map(int, input().split())
        if t == 0:
            addValue(i, j)
        else:
            anss.append(getRangeSum(i, j-1))

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


solve()

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

class BIT():
    def __init__(self, n, data):
        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 sub_sum(self, idx):
        a = 0
        while idx:
            a += self.bit[idx]
            idx -= (idx & (-idx))
        return a

    def sum(self, i, j):
        a = 0
        if j != 0:
            a += self.sub_sum(j)
        if i != 0:
            a -= self.sub_sum(i)
        return a

n,q=nii()
a=lnii()
bit=BIT(n,a)
for i in range(q):
    t,x,y=nii()
    if t==0:
        bit.add(x+1,y)
    else:
        print(bit.sum(x,y))

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


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

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

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


n, m = map(int, input().split())
c = list(map(int, input().split()))
b = BIT(n)
for i in range(n):
    b.add(i + 1, c[i])

res = []
for i in range(m):
    t, x, y = map(int, input().split())
    if t == 1:
        res.append(b.sum(y) - b.sum(x))
    else:
        b.add(x + 1, y)
print("\n".join(map(str, res)))

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


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

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

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


n, m = map(int, input().split())
c = list(map(int, input().split()))
b = BIT(n)
for i in range(n):
    b.add(i + 1, c[i])

res = []
for i in range(m):
    t, x, y = map(int, input().split())
    if t == 1:
        res.append(b.sum(y) - b.sum(x))
    else:
        b.add(x + 1, y)
print("\n".join(map(str, res)))

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


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

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

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


n, m = map(int, input().split())
c = list(map(int, input().split()))
b = BIT(n)
for i in range(n):
    b.add(i + 1, c[i])

res = []
for i in range(m):
    t, x, y = map(int, input().split())
    if t == 1:
        res.append(b.sum(y) - b.sum(x))
    else:
        b.add(x + 1, y)
print("\n".join(map(str, res)))

Solution (Python):
class bit:
  def __init__(self, n):
    self.size = n
    self.bit = [0] * (n + 1)
  
  def make(self, lst):
    self.bit = [0] + lst[:]
    for i in range(1, self.size + 1):
      if i + (i & -i) > self.size:
        continue
      self.bit[i + (i & -i)] += self.bit[i]
  
  def add(self, a, b):
    i = a + 1
    while i <= self.size:
      self.bit[i] += b
      i += i & -i
  
  def sum(self, a):
    i = a
    ret = 0
    while i > 0:
      ret += self.bit[i]
      i -= i & -i
    return ret
  
  def sub(self, a, b):
    return self.sum(b) - self.sum(a)

n, q = map(int, input().split())
lst = [int(i) for i in input().split()]
l = bit(n)
l.make(lst)
for _ in range(q):
  t, a, b = map(int, input().split())
  if t == 0:
    l.add(a, b)
  else:
    print(l.sub(a, b))

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

class BIT():
    def __init__(self, n, data):
        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 sub_sum(self, idx):
        a = 0
        while idx:
            a += self.bit[idx]
            idx -= (idx & (-idx))
        return a

    
    def sum(self, i, j):
        a = 0
        if j != 0:
            a += self.sub_sum(j)
        if i != 0:
            a -= self.sub_sum(i)
        return a

n,q=nii()
a=lnii()
bit=BIT(n,a)
for i in range(q):
    t,x,y=nii()
    if t==0:
        bit.add(x+1,y)
    else:
        print(bit.sum(x,y))

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

class BIT():
    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 sub_sum(self, idx):
        s = 0
        while idx:
            s += self.bit[idx]
            idx -= (idx & (-idx))
        return s

    def sum(self, i, j):
        a = 0
        if j != 0:
            a += self.sub_sum(j)
        if i != 0:
            a -= self.sub_sum(i)
        return a

n,q=nii()
a=lnii()
bit=BIT(n,a)
for i in range(q):
    t,x,y=nii()
    if t==0:
        bit.add(x+1,y)
    else:
        print(bit.sum(x,y))

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

class BIT():
    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=nii()
a=lnii()
bit=BIT(n,a)
for i in range(q):

    t,x,y=nii()
    if t==0:
        bit.add(x+1,y)
    else:
        print(bit.sum(y)-bit.sum(x))

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


class BIT():
    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=BIT(n,a)
for i in range(q):
    t,x,y=map(int,input().split())
    if t==0:
        bit.add(x+1,y)
    else:
        print(bit.sum(y)-bit.sum(x))

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

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * n

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

    def update(self, i, x):
        while i < self.n:
            self.data[i] += x
            i |= i + 1
        return


n, m = map(int, input().split())
c = list(map(int, input().split()))
b = BIT(n)
for i in range(n):
    b.update(i, c[i])

res = []
for i in range(m):
    t, x, y = map(int, input().split())
    if t == 1:
        res.append(b.sum(y) - b.sum(x))
    else:
        b.update(x, y)
print("\n".join(map(str, res)))

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

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

    def update(self, i, x):
        while i < self.n:
            self.data[i] += x
            i |= i + 1
        return


n, m = map(int, input().split())
c = list(map(int, input().split()))
b = BIT(n)
for i in range(n):
    b.update(i, c[i])

for i in range(m):
    t, x, y = map(int, input().split())
    if t == 1:
        print(b.sum(y) - b.sum(x))
    else:
        b.update(x, y)

Solution (Python):
















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

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

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

    def init(self, a):
        for i, x in enumerate(a):
            self.add(i, x)

    def initrng(self, a):
        self.add(0, a[0])
        for i in range(1,n):
            self.add(i, a[i]-a[i-1])

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

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
N,Q=map(int,input().split())
a=list(map(int,input().split()))
class BIT:
    def __init__(self,len_A):
        self.N = len_A + 10
        self.bit = [0]*(len_A+10)
    
    def query(self,i):
        res = 0
        while i:
            res += self.bit[i]
            i -= i&(-i)
        return res
    
    def update(self,i,x):
        idx = i+1
        while idx < self.N:
            self.bit[idx] += x
            idx += idx&(-idx)
    def __str__(self):
        return f"{self.bit}"
b=BIT(N)
for i in range(N):
    b.update(i,a[i])
for i in range(Q):
    p,q,r=map(int,input().split())
    if p:
        print(b.query(r)-b.query(q))
    else:
        b.update(q,r)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
N,Q=map(int,input().split())
a=list(map(int,input().split()))
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 __str__(self):
        return f"{self.bit}"
b=BIT(N)
for i in range(N):
    b.update(i,a[i])
for i in range(Q):
    p,q,r=map(int,input().split())
    if p:
        print(b.query(r-1)-b.query(q-1))
    else:
        b.update(q,r)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
N,Q=map(int,input().split())
a=list(map(int,input().split()))
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 __str__(self):
        return f"{self.bit}"
b=BIT(N)
for i in range(N):
    b.update(i,a[i])
for i in range(Q):
    p,q,r=map(int,input().split())
    if p:
        print(b.query(r-1)-b.query(q-1))
    else:
        b.update(q,r)