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




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)

class BinaryIndexedTree:
    def __init__(self, n):
        '''1-index'''
        self.size = n + 1
        self.data = [0] * self.size
        self.element = [0] * self.size
        self.depth = 1 << n.bit_length() - 1
    
    def build(self, array):
        for i, x in enumerate(array):
            self.add(i, x)

    def add(self, i, v):
        self.element[i] += v; i += 1 
        while i < self.size:
            self.data[i] += v
            i += i & -i
    
    def sum(self, i):
        ret = 0; i += 1 
        while i > 0:
            ret += self.data[i]
            i -= i & -i
        return ret
    
    def query(self, l, r=None):
        '''get sum [l, r)'''
        if r == None: return self.element[l]
        return self.sum(r) - self.sum(l-1)

    def lower_bound(self, v):
        if v <= 0: return 0
        k = self.depth; i = 0
        while k > 0:
            if i+k < self.size and self.data[i+k] < v:
                v -= self.data[i+k]
                i += k
            k >>= 1
        return i + 1
    
    def upper_bound(self, v):
        if v <= 0: return 0
        k = self.depth; i = 0
        while k > 0:
            if i+k < self.size and self.data[i+k] <= v:
                v -= self.data[i+k]
                i += k
            k >>= 1
        return i + 1

def Main():
    n, q = read_ints()
    bit = BinaryIndexedTree(n)
    a = read_int_list()
    bit.build(a)
    for _ in range(q):
        t, l, r = read_ints()
        if t == 0:
            bit.add(l, r)
        else:
            print(bit.query(l, ~-r))    

if __name__ == '__main__':
    Main()

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





class BIT:
    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N + 1)
        self.b = 1 << N.bit_length() - 1

    
    def add(self, a, w):
        x = a
        while(x <= self.N):
            self.bit[x] += w
            x += x & -x

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

    def cum(self, l, r):
        return self.get(r) - self.get(l)

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

N, Q = getNM()
A = getList()
query = [getList() for i in range(Q)]


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

for a, b, c in query:
    if a == 0:
        bit.add(b + 1, c)
    else:
        
        
        print(bit.cum(b + 1, c + 1))

Solution (Python):
import sys
input = sys.stdin.buffer.readline
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):
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)
for flag, l, r in queries:
    if flag:
        print(bit.sum(l, r))
    else:
        bit.add(l, r)

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):
def segfunc(x,y):
    return x+y

class SegmentTree():
    def __init__(self,A,n,ide_ele):
        self.ide_ele=ide_ele
        self.num =2**(n-1).bit_length()
        self.seg = [self.ide_ele]*2*self.num
        
        for i in range(n):
            self.seg[i+self.num-1]=A[i]
        
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=segfunc(self.seg[2*i+1],self.seg[2*i+2])

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

    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = segfunc(res,self.seg[p])
            if q&1 == 1:
                res = segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res,self.seg[p])
        else:
            res = segfunc(segfunc(res,self.seg[p]),self.seg[q])
        return res
N,Q = list(map(int,input().split()))
A = list(map(int,input().split()))
ST = SegmentTree(A,N,0)
for i in range(Q):
    n,p,x = list(map(int,input().split()))
    if n==1:
        print(ST.query(p,x))
    else:
        A[p] += x
        ST.update(p,A[p])

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





class BinaryIndexedTree:
  def __init__(self, n):
    self.bit = [0] * n

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

  def sum_sub(self, i):
    a = 0
    i += 1
    while i:
      a += self.bit[i-1]
      i -= i & -i
    return a

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

n,q=map(int,input().split())
a=list(map(int,input().split()))
Bit=BinaryIndexedTree(n)
for i in range(n):Bit.add(i,a[i])
for _ in range(q):
  t,a,b=map(int,input().split())
  if t==0:
    Bit.add(a,b)
  else:
    print(Bit.sum(a,b))

Solution (Python):
from sys import setrecursionlimit, stdin


def bit_add(bit, i, x):
    i += 1
    n = len(bit)
    while i <= n:
        bit[i - 1] += x
        i += i & -i


def bit_sum(bit, i):
    result = 0
    i += 1
    while i > 0:
        result += bit[i - 1]
        i -= i & -i
    return result


def query(bit, start, stop):
    if start == 0:
        return bit_sum(bit, stop - 1)
    else:
        return bit_sum(bit, stop - 1) - bit_sum(bit, start - 1)


readline = stdin.readline
setrecursionlimit(10 ** 6)

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

bit = [0] * N
for i in range(N):
    bit_add(bit, i, a[i])

result = []
for _ in range(Q):
    Query = readline()
    if Query[0] == '0':
        _, p, x = map(int, Query.split())
        bit_add(bit, p, x)
    elif Query[0] == '1':
        _, l, r = map(int, Query.split())
        result.append(query(bit, l, r))

print(*result, sep='\n')

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

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

        N:要素数
        """
        self.calc=lambda x,y:x+y
        self.unit=0

        N=max(N,len(L))

        k=1
        d=1

        while k<N:
            k*=2
            d+=1

        X=[None]+[0]*k

        self.num=k
        self.depth=d

        if L:
            for i in range(len(L)):
                p=i+1
                while p<=k:
                    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):
        """第k要素にx加え,更新を行う.

        k:数列の要素
        x:更新後の値
        index:先頭の要素の番号
        """
        p=k+(1-index)
        while p<=self.num:
            self.data[p]+=x
            p+=p&(-p)

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

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

        a=self.index(k,index)
        y=x-a

        self.add(k,y,index)

    def sub_array(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.__section(beta)-self.__section(alpha-1)

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

N,Q=map(int,input().split())
A=list(map(int,input().split()))
B=Binary_Indexed_Tree(N,A)

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

Solution (Python):




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)

class BinaryIndexedTree:
    def __init__(self, n):
        '''1-index'''
        self.size = n + 1
        self.data = [0] * self.size
        self.element = [0] * self.size
        self.depth = 1 << n.bit_length() - 1
    
    def build(self, array):
        for i, x in enumerate(array):
            self.add(i, x)

    def add(self, i, v):
        self.element[i] += v; i += 1 
        while i < self.size:
            self.data[i] += v
            i += i & -i
    
    def sum(self, i):
        ret = 0; i += 1 
        while i > 0:
            ret += self.data[i]
            i -= i & -i
        return ret
    
    def query(self, l, r=None):
        '''get sum [l, r)'''
        if r == None: return self.element[l]
        return self.sum(r) - self.sum(l-1)

    def lower_bound(self, v):
        if v <= 0: return 0
        k = self.depth; i = 0
        while k > 0:
            if i+k < self.size and self.data[i+k] < v:
                v -= self.data[i+k]
                i += k
            k >>= 1
        return i + 1
    
    def upper_bound(self, v):
        if v <= 0: return 0
        k = self.depth; i = 0
        while k > 0:
            if i+k < self.size and self.data[i+k] <= v:
                v -= self.data[i+k]
                i += k
            k >>= 1
        return i + 1

def Main():
    n, q = read_ints()
    bit = BinaryIndexedTree(n)
    a = read_int_list()
    bit.build(a)
    for _ in range(q):
        t, l, r = read_ints()
        if t == 0:
            bit.add(l, r)
        else:
            print(bit.query(l, ~-r))    

if __name__ == '__main__':
    Main()

Solution (Python):
def RSQ_add(i, x):
    while True:
        if i > n:
            break
        b[i] += x
        i += i & -i

def RSQ_getsum(i):
    s = 0
    while True:
        if i <= 0:
            break
        s += b[i]
        i -= i & -i
    return s

n, q = map(int, input().split())
a = list(map(int, input().split()))
b = [0] * (n + 1)
for i in range(n):
    RSQ_add(i + 1, a[i])
for _ in range(q):
    x, y, z = map(int, input().split())
    if x == 0:
        RSQ_add(y + 1, z)
    else:
        ans = RSQ_getsum(z) - RSQ_getsum(y)
        print(ans)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
NN = 19
BIT = [0] * (2 ** NN + 1)

def addbit(i, x=1):
    i += 1
    while i <= 2**NN:
        BIT[i] += x
        i += i & (-i)

def getsum(i):
    ret = 0
    while i != 0:
        ret += BIT[i]
        i -= i&(-i)
    return ret

N, Q = map(int, input().split())
A = [int(a) for a in input().split()]
for i, a in enumerate(A):
    addbit(i, a)

for _ in range(Q):
    a, b, c = map(int, input().split())
    if a == 0:
        addbit(b, c)
    else:
        print(getsum(c) - getsum(b))

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

class BIT:
	"""
	<Attention> 0-indexed.
	query ... return the sum [0 to m]
	sum ... return the sum [a to b]
	sumall ... return the sum [all]
	add ... 'add' number to element (be careful that it doesn't set a value.)
	search ... the sum version of bisect.right
	output ... return the n-th element
	listout ... return the BIT list
	"""
	def query(self, m):
		res = 0
		while m > 0:
			res += self.bit[m]
			m -= m&(-m)
		return res
	
	def sum(self, a, b):
		return self.query(b)-self.query(a)
	
	def sumall(self):
		bitlen = self.bitlen-1
		return self.query(bitlen)

	def add(self, m, x):
		m += 1
		bitlen = len(self.bit)
		while m <= bitlen-1:
			self.bit[m] += x
			m += m&(-m)
		return
	
	def search(self, a):
		tmpsum = 0
		i = 0
		k = (self.bitlen-1).bit_length()
		while k >= 0:
			tmpk = 2**k
			if i+tmpk <= self.bitlen-1:
				if tmpsum + self.bit[i+tmpk] < a:
					tmpsum += self.bit[i+tmpk]
					i += tmpk
			k = k - 1
		return i+1
	
	def output(self, a):
		return self.query(a+1)-self.query(a)
	
	def listout(self):
		return self.bit
	
	def __init__(self, a):
		self.bitlen = len(a)+1
		self.bit = [0]*(len(a)+1)
		for i, j in enumerate(a):
			self.add(i, j)

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

for _ in range(q):
	x, y, z = map(int,input().split())
	if x == 0:
		bit.add(y, z)
	else:
		print(bit.sum(y, z))

Solution (Python):
n, q = map(int, input().split())
BIT = [0] * (n + 1)
def add(i, x):
    while i <= n:
        BIT[i] += x
        i += i & -i
def query(i):
    s = 0
    while i > 0:
        s += BIT[i]
        i -= i & -i
    return s
a = list(map(int, input().split()))
for i in range(n):
    add(i + 1, a[i])
for i in range(q):
    x, y, z = map(int, input().split())
    if x == 0:
        add(y + 1, z)
    else:
        print(query(z) - query(y))

Solution (Python):
class SegmentTree: 
    def __init__(self,list,f=lambda x,y:x+y,inf=0):
        self.height=(len(list)-1).bit_length()+1 
        self.id=inf 
        self.tree=[self.id]*(2**self.height) 
        self.f=f
        for i in range(len(list)):
            self.tree[2**(self.height-1)+i]=list[i]
        for i in range(2**(self.height-1)-1,0,-1):
            self.tree[i]=self.f(self.tree[2*i],self.tree[2*i+1])
        
    def update(self,i,x): 
        i+=2**(self.height-1)
        self.tree[i]+=x
        while i>1:
            i//=2
            self.tree[i]=self.f(self.tree[2*i],self.tree[2*i+1])
    
    def query(self,l,r):
        l+=2**(self.height-1)
        r+=2**(self.height-1)
        lf,rf=self.id,self.id
        while l<r:
            if l&1:
                lf=self.f(lf,self.tree[l])
                l+=1
            if r&1:
                r-=1
                rf=self.f(self.tree[r],rf)
            l//=2
            r//=2
        return self.f(lf,rf)

n,q=map(int,input().split())
x=list(map(int,input().split()))
S=SegmentTree(x)
for i in range(q):
    a,b,c=map(int,input().split())
    if a==0:
        S.update(b,c)
    else:
        print(S.query(b,c))