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



Sample input:
5 5
1 2 3 4 5
1 0 5
1 2 4
0 3 10
1 0 5
1 0 3


Sample output:
15
7
25
6

Submission status: Accepted

Solution code:
from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math
import random
J=10**19
###############################################################################\n=17
n,q=INPUT()
A=INPUT()
T=[0]*(n+1)
def update(i,x):
    while(i<=n):
        T[i]+=x
        i+=i&(-i)
def query(i):
    ans=0
    while(i>0):
        ans+=T[i]
        i-=i&(-i)
    return ans
for i in range(n):
    update(i+1,A[i])
#print(*T)

for _ in range(q):
    s,l,r=INPUT()
    if s==0:
        update(l+1,r)
    else:
        print(query(r)-query(l))
    #print()

Submission status: Accepted

Solution code:
#####segfunc######                                                              
def segfunc(x,y):
    return x+y

def init(init_val):
    #set_val                                                                    
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built                                                                      
    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))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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

# Date [ 2020-09-11 22:06:11 ]
# Problem [ fenwicktree.py ]
# Author Koki_tkg

import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
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()

Submission status: Accepted

Solution code:
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):
        # param k: index(0-index)
        # param x: update value
        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): #[l, r) 0-index
        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)

Submission status: Accepted

Solution code:
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#e`fFMxbD#_d>`=+#OZPmEYOQu7x!jk!6oLz&xZ5jjV6RKrTtosZy6g-?b>$mwXj^Jxg(yuON0jjzgp$qXePvI!1vY|~x4+3G1*sYoc^rW~SE?dFp@5Z#k1Yxg*(h?SvgFt;NhcU<%dFw;BZo@!@@HaPH43kgtzd373#;*@=BC#Y=;&)u$e?5_aW0UY&75vcdN&B`0%Tx`ZEy?o0#1P)_l@uZ3k<S=uHX6c4~F-G|Dz*(!Yb(1xx%ht*lRKM3I^+fz@-bpg-+lwUG0>HKu=(Zqa&L3##F7et%`EoeInD`$75s6h%b>omLAf;vAOh{p#B~j?jgHUlaCK7nLP{kEobB$;gH%jx=Wu1dM-NdE%x5xV97snn#0W")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
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$^#gajF#A`FSPypj<G3D+MO57oWq$j<KY+Z4|`Oy0p8<;29?~tXeaV)(CQSyyK}4CaTFtPJe`%caMrCnETj=TerIft>I**z%a5%t;q2nU2-~@Vp0-!c<{9tB0HczJ-D5>j@1c)L&)?Nmh&|9(7r>)W<yp`xf?VlYEYeU~@*xWbQXOz?@(d`xpsoZCTc|?%?TDj*I+A>J1V;M>ThllY@(d484Rl(x|5n7Sargsu1-Hc65GR0ISf?fM=xb8g11GnIZyU^i{Nc4ZlbUlo+!MjT?@({4HCu$+E!69~f%|((L@{ar6Q!V?W`e}#Lc&M9!eXu+Cn828l1~@P!&AhUL|w78`?l|kxyN#D_5E@L(GomwK_=q8Z<#uKzv>j>1~!;%5*T+1@;{6=5Uyv7@E58k9T^Gxf@!VIS}VC$ldPNcE8thIgxB>*UD9T{5~e(RLwme1H7HH0DC4hGNY;e$(52R8kYGPkUs>YVF7?)w`<|M<r)VE+6ZX;1ZDO>!{@_?bn(uk`<$|w?z)#J>6B_")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
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;#V@NFbqz-ml=T>O<l<?dnpy_#?o-$BrH17S2!Z%yf2kz4-<9VUAMNU>%L5Ns8@@vV6Vjl{`iA?%b$m82A82r?XTBXVr+qEE=d~ciMC$zxV?;?AWLRXFFZiE7tKIgA|9|W9d${M;AfQ@2bZ=TH8m6gmG3P%OT`}hI+k%J6}{=fMJU=z;8zyII1Y}r*&jZkmU<Zy<?v7@KmE!y!p2<-i_f8suH(OvvHb0DsHS2U@_MysRNVNWWE#V|Ky|Va5@cV`yK6_LgRNRI2W5T;&zK_`K@t(?||s$I-tZVn5Rgv*j!ln6Q3aq#p6u)pn3A&S@ZA|`5CCnJng^fx@_vQn3{dR974>5=Pg8H-ua$gYwuUB5^k`eWIdqmDcJuo+#tA~F5xfAI-Qv__65^go26FrusT^d;g`TKU4hr->bf)qY=LpTdLwhZ2-QpFTuH?5ArpBW#^YYKDuPA+v-CAj5}Uc+0@?4-_#JW!Vd}7ver{v#cGq8Qo`|M*o^sicYjor%@ecrR")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
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`#Gf0Fz_kydwza)(ipvm`qy?^Ef1wBrQ{N7u|H^I;b2PD@-%5YNs6jo_Ld2K!&`3at~3;hLfM8w&+Sk-f3QqDn<h2m4M?rp?MIHW+5sDrzHqzBudxHHOOsI`3-uH(VmXD0NXB|>h(1(CK<QS<B256}22~Vl*gziAr%p%?tC8fRLU6R7ktr=2MAq>BSwLlY`7<G2t%f&r0(0ankP|?|tuqSh(bu2_gOah#yAbqZ=6r85xDl}4fQl@!t=PeQ1Lw$&zYBPUg@|?uz1s)*C&LHA|Ir0}K_2z$y|8Z>_gYN7qQUxT;mR+;FP*}1I^vZ0RF1-sCMRLLJ5!A|s4CR>nKDI+upV6FiUtYtoO&dYV|(p4rQBm`cue7w+G6~n+3ZEKZ#AQr6%GWS(H|U%_+0ipSaiYSfZ!iL*V3{")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
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`#Gf0Fz}`6d(ZZ>lg8*h)W5dVYI!J4DJ7Rsi~T_x3kOrGmZwSMMN(AtvbRj=8{cwUccq~y6v{RfdTuM{zm{od)1+p+0jX8H{m3zj9k3DfdD|kt#ttwqO+tPa(y7PDsK@%)R%HZ~ZiQT>31Hl)ib4$=$OC-pgyc|+A|Dl!quY#3uxOB3!~5q7D#Od4iSgBHc!MH`IcgTD38dlH83py|YtVv0$ynxH2zoJdzBd`%2v~1GMV8oB>|nlub7aT=3wVWvh;|3P+lTT`h7W@OqYL<gJnGf^!oFeLYcchT2J54RE58K4bPC7mh*RR-I0{3WoP_P}Of}kIRiVbWlPR(a>%lb^G?XCErAHDuw%2|W<Q}2n5yC6AtMNf*vlq#})r?+NI1s!>e{dwybJ_D?(FKbGl7FDa&m8")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
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#x+#7<(>*x)#U{=VzlC8n?^XJ#@xyLPSB4ytd{DmmX5x)6d1sQ7NLw1K@YWW(a9wj#mHYTg;j)tPUYsoFvl6mn^50v$6$+2i5!?S1{aM!-<jn>eZ{t3fE)Y@RZ##TKXst-)rI`Pu^h9!K6MalaF|@H~rCZ-Korl1x&Ns^KD!BfvUSC4mZ7kU99+a=~EXMYc*L{Uk{`!n{Ui36IY?l$sS^BV*kvc)%bqMa>K~j?~QbT0-S>4T@7JC{1h%PJY9jE<?IB9F{APK_t52TbQok6vVOL9PVMpgLOjJ@0|UO;ho_B=p0@k3wm|d*ftD%&Bk8AU|q0qX_sJ^PT(*eaZ0?dp1=@CM{e4SP_@$N%B6o-iA;019$e#sIE(bQ^pFOL&0oI}>aU^U8p10zxqqz5<WA5JIU&C*98$bSd+5_Z&qT*u#NI_5ko*DG!`1i")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
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`#B9O={jEs&(HSrOIo83(0tootM#!mm6TjUBMwJxEF4XxI-Vx2CrME^>%lUiZ~2bfrmqY|qENP_FmPKt|Fujzn<fq8El91p-CK@P?14?7uM1$l2dqhxP@9EP>M=5Lu{VxX83Cm`A<HxYj9aRv(7+b*0H1pyITRDgM~%rzX+~yPw3ykz>w5{c;nmli@!cADfg*<`a#qL*NyDu(3YtmRs0D+HvCOLw^eX0ZFEXeRu-Sr&B(a^?!*UCkNRIy(@C+*v`38eKg!ca|9|(U}7w`djG;8pU{lIwEYMvD>HbjOiZ-O_S!f8I@mUuUg!k8v!Vf#B#tv1+IsOjBgij=_~w6UO}1^J(PB9UVIJ8y>EBQ!ojc%`<S9%Ht6lI&A0=+(lJ;5GV#BN3m=fd`2$NE|Ww0}2q%VE")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
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|#%=l^y-k``~=`<^+38WErFbde@Yt+c0;ym*%kY3GP?o9?a2%9aa$P(Y-9+q3UM0Wf)!YiyW$^!b~5XwIpJ_!Dgj_?I})T{S}eZ#odYVH*c)<=OWAA%2^!fC#`DJ_M8!k8v!wB4PlMjKZZ)wKIekut>NVk~GVL7q!bByw#3`pwYr2#t@BTd6Il2bC>eB!>mPCO8teMSmGcBp0$5!Ql`bj*k2V((Sr6")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
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#aPf#g8VN%k;t+A?KeZiBQ!ojZl$)I9#pn?lKfLG=rzKTxHbCAKq9@6y$BYEU~zQh52KB`-v")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
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#Vj8nGL_^M4zo0qcjEtbkV!bH+hSy->6Ev?y?;e#6QeiqMVGK8xj)qyQj>AE(2@R^9^U?!mSfl5irYmBQzc9(Bey}=sxzH>UM2GwEnN7{sAc#1N}m=zbMG**D`gwa72eG9X%?w9YfLU%IiKoPNMLYRS*EhbKiFdH;n^R=<-=>+)cy;TUx%9LO@{+iFfY<GhuKVvdCj=(Lh@aT;OsdW#6fGxa_=oV7f_Q(pzugI|P<J@w=?MiFWf--IJku4&x3kMNTUKNS7@&9>^q#79o3)!z4CX}s}ar4D(gBk4wDA>T`xqNDjMR*!@xMw&R&qwJ^#pE~qdgir7l!q(HZVDdY=@FK!S+V8}BT~n!Qlnf(fXnh6Pr%#tlLT}Ej)U~m{H=HO4j%S~Snlxj4V~vLoD4OeTCRKq!`BXTWD#dKRP-AX=bIPbOWziwiO?nHwbb2~j<+SA8Lfxq%<q3#{ny=#K0^Kza=(j_8u=%`2JGo{@(;l+ACd")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
code = r"""
# distutils: language=c++
# distutils: include_dirs=[/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include,/opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False
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')

Submission status: Accepted

Solution code:
code = r"""
# distutils: language=c++
# distutils: include_dirs = [/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
library = """
# distutils: language=c++
# distutils: include_dirs=[/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False
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)))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
def input(): return sys.stdin.readline().rstrip()

# ライブラリ参照https://ikatakos.com/pot/programming_algorithm/data_structure/binary_indexed_tree
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()

Submission status: Accepted

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


class BinaryIndexTree:  # 1-indexed
    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))

Submission status: Accepted

Solution code:
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):
	#N:処理する区間の長さ
	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

	# セグメント木の中身をリストAで初期化
	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])

	#k番目の値をxに更新
	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])

	# k番目の値を取得
	def pointQuery(self, k):
		return self.data[k + self.N0 - 1]

	# k番目の値にxを加算
	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])

	#区間[l, r]の演算値
	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()

Submission status: Accepted

Solution code:
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  # 1-indexed の時は pos = 0
        if equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] <= x:  # 1-indexed の時は k <= self.n
                    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:  # 1-indexed の時は k <= self.n
                    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)

Submission status: Accepted

Solution code:
# Binary Indexed Tree (Fenwick Tree)
class BIT:
    # 1-index
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i): #[0, 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

#pypyで提出すると良い。足算をするだけならbit木

#例題
## https://atcoder.jp/contests/practice2/tasks/practice2_b

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 #1-index
    x = u
    B.add(p, x)
  else:
    l = t + 1
    r = u + 1
    print(B.sum(r-1) - B.sum(l-1))