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 BinaryIndexedTree:
    
    def __init__(self, n):
        self.size = n
        self.data = [0] * (n+1)

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

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

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

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

    bit = BinaryIndexedTree(n)
    for i, ai in enumerate(a):
        bit.add(i, ai)

    ans = []
    for _ in range(q):
        typ, i, j = map(int, input().split())
        if typ == 0:
            bit.add(i, j)
        else:
            ans.append(bit.cumulative_sum(j) - bit.cumulative_sum(i))

    for i in ans:
        print(i)

main()

Solution (Python):
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

class BIT:
    """ Binary Indexed Tree """

    def __init__(self, n):
        self.n = n
        
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def query(self, l, r):
        """ 区間和の取得 [l, r) """
        return self.sum(r-1) - self.sum(l-1)
    
    def get(self, i):
        """ 一点取得 """
        return self.query(i, i+1)

    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        self.add(i, x - self.get(i))

    def print(self):
        for i in range(self.n):
            print(self.get(i), end=' ')
        print()

N, Q = MAP()
A = LIST()
bit = BIT(N)
for i in range(N):
    bit.add(i, A[i])

for i in range(Q):
    q, a, b = MAP()

    if q == 0:
        bit.add(a, b)
    else:
        ans = bit.query(a, b)
        print(ans)

Solution (Python):
class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    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 query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
      
N,Q=map(int,input().split())
*A,=map(int,input().split())
bit = BIT(N)
for i in range(N):
  bit.add(i+1,A[i])
for i in range(Q):
  q,a,b = map(int,input().split())
  if q:
    print(bit.query(a,b))
  else:
    bit.add(a+1,b)

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

class BIT():
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

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

	def Add(self, i, x):
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

n, q = map(int, input().split())
fw = BIT(n+2)
a = list(map(int, input().split()))
for i, x in enumerate(a):
	fw.Add(i+1, x)
for _ in range(q):
	x, y, z = map(int, input().split())
	if x == 0:
		fw.Add(y+1, z)
	else:
		print(fw.Sum(z) - fw.Sum(y))

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

class BIT():
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

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

	def Add(self, i, x):
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

n, q = map(int, input().split())
fw = BIT(n+2)
a = list(map(int, input().split()))
for i, x in enumerate(a):
	fw.Add(i+1, x)
for _ in range(q):
	x, y, z = map(int, input().split())
	if x == 0:
		fw.Add(y+1, z)
	else:
		print(fw.Sum(z) - fw.Sum(y))

Solution (Python):
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,input().split())
Binit(BIT,N+1)
A=list(map(int,input().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,input().split())
  if a:
    print(Bssum(BIT,b+1,c))
  else:
    Badd(BIT,b+1,c)

Solution (Python):
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

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

@njit((i8[:], ), cache=True)
def build(raw_data):
    bit = raw_data.copy()
    for i in range(len(bit)):
        j = i + (i & (-i))
        if j < len(bit):
            bit[j] += bit[i]
    return bit


@njit((i8[:], i8), cache=True)
def get_sum(bit, i):
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s


@njit((i8[:], i8, i8), cache=True)
def add(bit, i, x):
    while i < len(bit):
        bit[i] += x
        i += i & -i


@njit((i8[:], i8), cache=True)
def find_kth_element(bit, k):
    N = len(bit)
    x, sx = 0, 0
    dx = 1
    while 2 * dx < N:
        dx *= 2
    while dx:
        y = x + dx
        if y < N:
            sy = sx + bit[y]
            if sy < k:
                x, sx = y, sy
        dx //= 2
    return x + 1

@njit((i8[:], i8[:]), cache=True)
def main(X, TAB):
    bit = build(X)
    for i in range(0, len(TAB), 3):
        t, a, b = TAB[i:i + 3]
        if t == 0:
            add(bit, a + 1, b)
        else:
            x = get_sum(bit, b) - get_sum(bit, a)
            print(x)

N, Q = map(int, readline().split())
X = np.array([0] + readline().split(), np.int64)
TAB = np.array(read().split(), np.int64)

main(X, TAB)

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
    read = sys.stdin.buffer.read
    N, Q = map(int, input().split())
    seg = BIT(list(map(int, input().split())))
    for _ in range(Q):
        a, b, c = map(int, input().split())
        if a:
            print(seg.folded(b, c))
        else:
            seg.point_append(b, c)

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 + (i & -i)] + self.data[i]        

    def point_append(self, index, delta):
        index += 1
        while index < self.n:
            self.data[index] = 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
    read = sys.stdin.buffer.read
    N, Q = map(int, input().split())
    seg = BIT(list(map(int, input().split())))
    for _ in range(Q):
        a, b, c = map(int, input().split())
        if a:
            print(seg.folded(b, c))
        else:
            seg.point_append(b, c)

if __name__ == "__main__":
    main()

Solution (Python):
class BIT():

    __slots__ = ["func", "e", "n", "data"]

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

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

def main():
    import sys
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read
    N, Q = map(int, input().split())
    seg = BIT(list(map(int, input().split())), lambda a, b: a + b, 0)
    for _ in range(Q):
        a, b, c = map(int, input().split())
        if a:
            print(seg.prefix_folded(c) - seg.prefix_folded(b))
        else:
            seg.point_append(b, c)

if __name__ == "__main__":
    main()

Solution (Python):
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [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):
        
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def subtract(self, i, x):
        self.add(i, -x)
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    
    def lower_bound(self, x):
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) >= x:
                r = index
            else:
                l = index
                
        if self.sum(l) >= x:
            return l
        return r
    
    def upper_bound(self, x):
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) <= x:
                l = index
            else:
                r = index
                
        if self.sum(r) <= x:
            return r
        return l
    

def main():
    n, q = map(int, input().split())
    bit = BIT(n)
    a = list(map(int, input().split()))
    for i, v in enumerate(a):
        bit.add(i+1, v)

    for i in range(q):
        query = list(map(int, input().split()))
        if query[0] == 0:
            p, x = query[1:]
            bit.add(p+1, x)
        else:
            l, r = query[1:]
            res = bit.get_sum(l, r)
            print(res)


if __name__ == "__main__":
    main()

Solution (Python):
class Fenwick:
    def __init__(self, n):
        self.n = n
        self.BIT = [0] * (n + 1)
    
    def getsum(self, i):
        ret = 0
        i += 1
        while(i > 0):
            ret += self.BIT[i]
            i -= i & -i
        return ret
    
    def add(self, i, x):
        i += 1
        while(i <= self.n):
            self.BIT[i] += x
            i += i & -i

N, Q = map(int, input().split())
A = list(map(int, input().split()))
bit = Fenwick(N)
for i in range(N):
    bit.add(i, A[i])

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

Solution (Python):
class Fenwick:
    def __init__(self, n):
        self.n = n
        self.BIT = [0] * (n + 1)
    
    def getsum(self, i):
        ret = 0
        i += 1
        while(i > 0):
            ret += self.BIT[i]
            i -= i & -i
        return ret
    
    def add(self, i, x):
        i += 1
        while(i <= self.n):
            self.BIT[i] += x
            i += i & -i

N, Q = map(int, input().split())
A = list(map(int, input().split()))
bit = Fenwick(N)
for i in range(N):
    bit.add(i, A[i])

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

Solution (Python):
N,Q = map(int,input().split())
BIT = [0]*(N+1)

def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

a = list(map(int,input().split()))
for i in range(N):
    BIT_update(i+1,a[i])

for i in range(Q):
    a,b,c = map(int,input().split())
    if a == 0:
        BIT_update(b+1,c)
    else:
        print(BIT_query(c)-BIT_query(b))

Solution (Python):
class fenwick_tree:
    def __init__(self, n=0, T=int):
        self._n = n
        self.data = [T() for _ in range(n)]
        self.T = T
    
    def add(self, p, x):
        p += 1
        while p <= self._n:
            self.data[p - 1] += x
            p += p & -p
    
    def sum(self, l, r):
        return self._sum(r) - self._sum(l)
    
    def _sum(self, r):
        s = self.T()
        while r > 0:
            s += self.data[r - 1]
            r -= r & -r
        return s

import sys
input = sys.stdin.readline
n, q = map(int, input().split())
t = fenwick_tree(n)
a = list(map(int, input().split()))
for i in range(n):
    t.add(i, a[i])
for _ in range(q):
    qtype, op1, op2 = map(int, input().split())
    if qtype == 0:
        t.add(op1, op2)
    else:
        print(t.sum(op1, op2))

Solution (Python):
import sys

input = sys.stdin.buffer.readline


class FenwickTree:
    """FenwickTree (Binary Indexed Tree, 0-index)

    Queries:
        1. add(i, val): add val to i-th value
        2. sum(n): sum(bit[0] + ... + bit[n-1])

    complexity: O(log n)

    See: http://hos.ac/slides/20140319_bit.pdf
    """

    def __init__(self, a_list):
        self.N = len(a_list)
        self.bit = a_list[:]
        for _ in range(self.N, 1 << (self.N - 1).bit_length()):
            self.bit.append(0)
        for i in range(self.N-1):
            self.bit[i | (i+1)] += self.bit[i]

    def add(self, i, val):
        while i < self.N:
            self.bit[i] += val
            i |= i + 1

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

    def query(self, low, high):
        return self.sum(high) - self.sum(low)


def yosupo():
    
    _, Q = map(int, input().split())
    fwt = FenwickTree([int(x) for x in input().split()])
    ans = []
    for _ in range(Q):
        type_, l, r = map(int, input().split())
        if type_ == 0:
            fwt.add(l, r)
        else:
            ans.append(fwt.query(l-1, r-1))
    print(*ans, sep="\n")


def aoj():
    
    N, Q = map(int, input().split())
    fwt = FenwickTree([0] * N)
    for _ in range(Q):
        type_, l, r = map(int, input().split())
        if type_ == 0:
            fwt.add(l-1, r)
        else:
            print(fwt.query(l-2, r-1))


if __name__ == "__main__":
    yosupo()

Solution (Python):
import sys

input = sys.stdin.buffer.readline


class FenwickTree:
    """FenwickTree (Binary Indexed Tree, 0-index)

    Queries:
        1. add(i, val): add val to i-th value
        2. sum(n): sum(bit[0] + ... + bit[n-1])

    complexity: O(log n)

    See: http://hos.ac/slides/20140319_bit.pdf
    """

    def __init__(self, a_list):
        self.N = len(a_list)
        self.bit = a_list[:]
        for _ in range(self.N, 1 << (self.N - 1).bit_length()):
            self.bit.append(0)
        for i in range(self.N-1):
            self.bit[i | (i+1)] += self.bit[i]

    def add(self, i, val):
        while i < self.N:
            self.bit[i] += val
            i |= i + 1

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

    def query(self, low, high):
        return self.sum(high) - self.sum(low)


def yosupo():
    
    _, Q = map(int, input().split())
    fwt = FenwickTree([int(x) for x in input().split()])
    for _ in range(Q):
        type_, l, r = map(int, input().split())
        if type_ == 0:
            fwt.add(l, r)
        else:
            print(fwt.query(l-1, r-1))


def aoj():
    
    N, Q = map(int, input().split())
    fwt = FenwickTree([0] * N)
    for _ in range(Q):
        type_, l, r = map(int, input().split())
        if type_ == 0:
            fwt.add(l-1, r)
        else:
            print(fwt.query(l-2, r-1))


if __name__ == "__main__":
    yosupo()

Solution (Python):
import sys

input = sys.stdin.buffer.readline


class FenwickTree:
    """FenwickTree (Binary Indexed Tree, 0-index)

    Queries:
        1. add(i, val): add val to i-th value
        2. sum(n): sum(bit[0] + ... + bit[n-1])

    complexity: O(log n)

    See: http://hos.ac/slides/20140319_bit.pdf
    """

    def __init__(self, a_list):
        self.N = len(a_list)
        self.bit = a_list[:]
        for _ in range(self.N, 1 << (self.N - 1).bit_length()):
            self.bit.append(0)
        for i in range(self.N-1):
            self.bit[i | (i+1)] += self.bit[i]

    def add(self, i, val):
        while i < self.N:
            self.bit[i] += val
            i |= i + 1

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

    def query(self, low, high):
        return self.sum(high) - self.sum(low)


def yosupo():
    
    _, Q = map(int, input().split())
    fwt = FenwickTree([int(x) for x in input().split()])
    for _ in range(Q):
        type_, l, r = map(int, input().split())
        if type_ == 0:
            fwt.add(l, r)
        else:
            print(fwt.query(l-1, r-1))


def aoj():
    
    N, Q = map(int, input().split())
    fwt = FenwickTree([0] * N)
    for _ in range(Q):
        type_, l, r = map(int, input().split())
        if type_ == 0:
            fwt.add(l-1, r)
        else:
            print(fwt.query(l-2, r-1))


if __name__ == "__main__":
    yosupo()

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def main():
    
    N = bit = None

    def init(n):
        nonlocal N, bit
        N = n
        bit = [0] * (N + 1)  

    def bit_add(pos, val):
        assert pos > 0
        x = pos
        while x <= N:
            bit[x] += val
            x += x & -x  

    def bit_sum(pos):
        ret = 0
        x = pos
        while x > 0:
            ret += bit[x]
            x -= x & -x
        return ret

    
    N, Q = map(int, input().split())
    init(N)
    AS = list(map(int, input().split()))
    for i, a in enumerate(AS):
        bit_add(i + 1, a)

    for _q in range(Q):
        a, b, c = map(int, input().split())
        if a == 0:
            bit_add(b + 1, c)
        else:
            print(bit_sum(c) - bit_sum(b))



T1 = """
5 5
1 2 3 4 5
1 0 5
1 2 4
0 3 10
1 0 5
1 0 3
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
15
7
25
6
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)



def init(n):
    global N, bit
    N = n
    bit = [0] * (N + 1)  


def bit_add(pos, val):
    assert pos > 0
    x = pos
    while x <= N:
        bit[x] += val
        x += x & -x  


def bit_sum(pos):
    ret = 0
    x = pos
    while x > 0:
        ret += bit[x]
        x -= x & -x
    return ret


def bit_bisect(lower):
    "find a s.t. v1 + v2 + ... + va >= lower"
    x = 0
    k = 1 << (N.bit_length() - 1)  
    while k > 0:
        if (x + k <= N and bit[x + k] < lower):
            lower -= bit[x + k]
            x += k
        k //= 2
    return x + 1


def main():
    
    N, Q = map(int, input().split())
    init(N)
    AS = map(int, input().split())
    for i, a in enumerate(AS):
        bit_add(i + 1, a)

    for _q in range(Q):
        a, b, c = map(int, input().split())
        if a == 0:
            bit_add(b + 1, c)
        else:
            print(bit_sum(c) - bit_sum(b))



T1 = """
5 5
1 2 3 4 5
1 0 5
1 2 4
0 3 10
1 0 5
1 0 3
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
15
7
25
6
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)



def init(n):
    global N, bit
    N = n
    bit = [0] * (N + 1)  


def bit_add(pos, val):
    assert pos > 0
    x = pos
    while x <= N:
        bit[x] += val
        x += x & -x  


def bit_sum(pos):
    ret = 0
    x = pos
    while x > 0:
        ret += bit[x]
        x -= x & -x
    return ret


def bit_bisect(lower):
    "find a s.t. v1 + v2 + ... + va >= lower"
    x = 0
    k = 1 << (N.bit_length() - 1)  
    while k > 0:
        if (x + k <= N and bit[x + k] < lower):
            lower -= bit[x + k]
            x += k
        k //= 2
    return x + 1


def main():
    
    N, Q = map(int, input().split())
    init(N)
    AS = list(map(int, input().split()))
    for i, a in enumerate(AS):
        bit_add(i + 1, a)

    for _q in range(Q):
        a, b, c = map(int, input().split())
        if a == 0:
            bit_add(b + 1, c)
        else:
            print(bit_sum(c) - bit_sum(b))



T1 = """
5 5
1 2 3 4 5
1 0 5
1 2 4
0 3 10
1 0 5
1 0 3
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
15
7
25
6
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Solution (Python):
class BIT:
            
    def __init__(self, L):
        self.N = len(L)
        self.bit = [0]*self.N
        for i,l in enumerate(L):
            self.add(i,l)
        self.N0 = 1
        while self.N0*2 <= self.N:
            self.N0 *= 2

    def add(self, a, w):
        x = a + 1
        for i in range(1000):
            self.bit[x-1] += w
            x += x & -x
            if x > self.N:
                break

    def sum(self, a):
        x = a+1
        ret = 0
        for i in range(1000):
            ret += self.bit[x-1]
            x -= x & -x
            if x <= 0:
                break        
        return ret

    
    def lower_bound(self, w):
        if w<=0:
            return 0
        x = 0
        k = self.N0
        while k>0:
            if x+k<=self.N:
                if self.bit[x+k-1]<w:
                    w-=self.bit[x+k-1]
                    x+=k
            k//=2
        return x


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

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

Solution (Python):
class fenwick_tree():
    n=1
    data=[0 for i in range(n)]
    def __init__(self,N):
        self.n=N
        self.data=[0 for i in range(N)]
    def add(self,p,x):
        assert 0<=p<self.n,"0<=p<n,p={0},n={1}".format(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 and l<=r and r<=self.n),"0<=l<=r<=n,l={0},r={1},n={2}".format(l,r,self.n)
        return self.sum0(r)-self.sum0(l)
    def sum0(self,r):
        s=0
        while(r>0):
            s+=self.data[r-1]
            r-=r&-r
        return s

N,Q=map(int,input().split())
a=[int(i) for i in input().split()]
FT=fenwick_tree(N)
for i in range(N):
    FT.add(i,a[i])
for i in range(Q):
    t,a,b=map(int,input().split())
    if t==0:
        FT.add(a,b)
    else:
        print(FT.sum(a,b))

Solution (Python):
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
A = I[2:2 + N]
XYZ = I[2 + N:]
X, Y, Z = XYZ[::3], XYZ[1::3], XYZ[2::3]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)
for idx, val in enumerate(A):
    BIT.add(idx + 1, val)
for x, y, z in zip(X, Y, Z):
    if x:
        print(BIT.sum(z) - BIT.sum(y))
    else:
        BIT.add(y + 1, z)

Solution (Python):
from typing import Optional, Sequence


class BinaryIndexedTree:
    """Binary Indexed Tree (Fenwick Tree): O(logN)

    References:
        http://hos.ac/slides/20140319_bit.pdf
    """

    __slots__ = ["_size", "_tree", "is_zero_origin"]

    def __init__(
        self,
        size: int,
        initial_values: Optional[Sequence[int]] = None,
        is_zero_origin: bool = True,
    ):
        self._size = size
        self._tree = [0] * (size + 1)
        self.is_zero_origin = is_zero_origin

        if initial_values:
            for i, a in enumerate(initial_values):
                self.add(i, a)

    def add(self, index: int, value: int) -> None:
        """Add value to tree[index], O(logN)."""
        if self.is_zero_origin:
            index += 1
        while index <= self._size:
            self._tree[index] += value
            index += index & -index

    def sum(self, index: int) -> int:
        """Return the sum of [1, index] in O(logN)."""
        ret = 0
        while index > 0:
            ret += self._tree[index]
            index -= index & -index
        return ret

    def range_sum(self, left: int, right: int) -> int:
        """Return the range sum of [left, right] in O(logN)."""
        if not self.is_zero_origin:
            left -= 1
        return self.sum(right) - self.sum(left)


def point_add_range_sum():
    
    N, Q, *X = map(int, open(0).read().split())
    A, queries = X[:N], X[N:]
    tree = BinaryIndexedTree(N, A)
    res = []
    for com, x, y in zip(*[iter(queries)] * 3):
        if com:
            res.append(tree.range_sum(x, y))
        else:
            tree.add(x, y)
    print("\n".join(map(str, res)))


if __name__ == "__main__":
    point_add_range_sum()