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

    #i, j is 1-indexed, not 0-origin
    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))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

# Binary Indexed Tree
# 1-indexed
# sum(r)        :閉区間 [0,r] の合計を取得する
# [8] a0 ・ a1  ・ a2 ・ a3 ・ a4 ・ a5 ・ a6 ・ a7
# [4] a0 ・ a1  ・ a2 ・ a3
# [2] a0 ・ a1               [6] a4 ・ a5
# [1] a0       [3] a2        [5] a4        [7] a6

#                   [1000]
#           [0100]
#   [0010]                [0110]
# [0001]    [0011]      [0111]      [1111]

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

Submission status: Accepted

Solution code:
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)
    # sum(A[0] ~ A[i-1])
    def query(self,i):
        res = 0
        while i:
            res += self.bit[i]
            i -= i&(-i)
        return res
    # A[i] += x
    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)

Submission status: Accepted

Solution code:
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)
    # sum(A0 ~ Ai)
    # O(log N)
    def query(self,i):
        res = 0
        idx = i+1
        while idx:
            res += self.bit[idx]
            idx -= idx&(-idx)
        return res
    # Ai += x
    # O(log N)
    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)

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*A8ul{!K_BJEm?@{7xn?pm|6-nE3KA-?(cVNnbc{Y$~}j3&po#jU_Z9jDg#MX)zOM?CGWY+U*c$T!T8A<x@EfA3(2?CRBb-{ENN@ws5H76c=J6qR7x&^iDs{jg}p&hK9Ho?v3Y9?p)YvFEvu;^NEFJJal{H<g4C*7zb)`AH&6^k#PK(kq@Z*qWEMw&=K}2rFvwxy%f}jh!g3(FvqNy`mZW1@l!&b0^*w`~;q-e%oEn2?ST10SoEdUFXt?c+0yg;SwJ3lVMdDltayE0iHtF36SmmGsOT}7jV4A}zu;ac3Ji<%_SwP!0UjEMTp74Kk0UxjkdbLj2H4J;r#$Lf-Z4kI}A-K>99L6h7X$f=$`ZziYTVI(fwLw*(hTSJB&3rr<<C1uZ^gi{F29E7tzp>QamipTguGD73gG!zrWbvh*$T`A3#WlK1mj-+;Tkb7(-eQm7FR^{mdj')))
    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!EWj>5WFMt4=bvtLJ2Wdd#F&;Uw9X8eF!=B1}q%gwH=^;|JF%>RK=GhGvnFa**t($AvRIzuma7^uHic@#C$#;J%IR*duwj^R^t(M@iOG_96jF(TRWw3%l$4Ci@y~QF^LA=$_U*^+)Cv`@yYhKMkcI@7$P^3<=P6anN}rpt@BI%#)68ta9kXyc3`Hd-8bFw$a=F3n01lyD6B-k2vKjwBO$R$U7<Hnd0WHey%(?w%}I$v^oSo5FucY<?g*1!Fj<X9K&Q13&I!#!fd1AtUHe>bdQCb*W~xjCGrN&Tt0ZtKTf$|qhVy`3Lul%j(ix<OCvrS$8>SFM9->qhgsPqO5q22Gp8E`(Cvi0pI+q_&MC-5G?z0a<8LbR<6_Cs6Y&c><%M1h*u<YQ|p0)_jgBeRA`|8sfEa3I+#;J<vcUZ2VB=f_KNR9%Y;CTsiC_CI^Y-lCo+8D(}vaYKPz6S3qOM#uUl+9(3A6wAY>^AUJsz|pCp6;;Iw2O*jQB(>%{lQ2Ob*f_CZYAr>{g!=QLZbP8gqDuJ_Ibnn9jsf_^zo0D|IB07)=eu<Bh7jp>VN}lcgN;@2fK`rG9vgt%e@>0')))
    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!EWj>5WFMt4=bvtLJ2Wdd#F&;Uw9X8eF!=B1}q%gwH=^;|JF%>RK=GhGvnFa**t($AvRIzuma7^uHic@#C$#;J%IR*duwj^R^t(M@iOG_96jF(TRWw3%l$4Ci@&X6V62SLjl``~J`|s9Z);@2nusBC6IrgU;F@VwGS}L^<ZmpfhzrNXfeHs^n%aHS9gnOx%Ya!I8IQtB^otPnW;_xStJD&D1C_TmOx}9|tI(X3I7E;5F#*GC4CIb5=>?P3cm#A>3*ns5JOt=(ZPT^S^`_UPGi0X9L@=`(d9+Fbm$D^X25UGE*foTvZYiBXdUztoqqboRLF6GyWkIOgSs!7CQS7<Tz<Cl^1EF*I5k<8As_j1eAe7O{U{?XToX&<LCbY~zKmp4RKJ96R@I08YB(kqQoxuWL-)@|$h<=CV3Q96R+=%2T;0d0WFo&|kJ;sJsBCd^5TqNtd%HV78uCf%^IZN4G2KliCZOv{2Po;`<%i!q_J59T&C>BMfz|-%G1W~6d=IvIpzT9uw*CiyH??-6q=xd)h%-_MfMNJ?7X!*}PW^LWH@-)({*P#wLuy%KB&UdiO2q`0i{{vzi8j1')))
    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(Qe`}5PV1CA68VSh7w|`-b01TeFbklgdBSV7LM)O4$!~9brMLb!!N+h?CkC=Pasu@O;kFpL349x_yIR!v6xPtKzzreH3Poact*W>OWdeT8KE1Ad#QZbe6pjhkqK)ehR981g|>ogrd7#YYxq{Yv!Eg_9Tz9E4a_vP`=%O?tT)SnSr-|P!b<eZ5cO_45fUrFYea9L^0tQAM=xL%nu`*r=n?<S!0;Laxg*Sa!E8O90KL{iI43j@0s5+aD*N2-dQEy`CQ~MYnGfXIDhXW5mT)<2;W}cs5SqHBbPnmm6FHr<15*g12vI5vLe<Xt2nUSf$bAmZleiiQoh!~LqV;!e_p=W|8LbR<9gxdxK3*}QWex&1u<GE;QE7zN(T*jNefMk*OZfdhaH=Bu16FG&$^0}B$x*-yyslsYWrur=4V^^X2cx)1)=ibe*XX;-Q()ITWpi8P#}%|ShaJ3>DpHlf%L6t`x2Px<MXkWopA!k9NmVS`tK@yV|7BmdkZ8Xjp{1wqa}Jn)fOUt;o_}fi*F5KK-*ob{(!AH94mh%Q4{WXvu-ghLBZB_{Vi^wI')))
    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${rgL2iRE5WGj?4|8b)jT3>?N)<}_ku(P|23B=UVhl-tUpuA&n(hTNJKh<OUFzlt{%z_;ZBCiaq!bdIj;BT&oOGrt5iCkal9cmJYYJ-a{Yn^KXPQ|eDN_auUWgL1QPut}wv`-E3?L~<O4yIFyHyxLH5JJ;Sisi6FvuA=c8EQEsYwbX1Iblxn}cW=jWCtAv&HLsid>8AYwWmb94|;>tSo13Ilifd>9hi$+v^)DkQGJf%n-YIy3W0NQ-tjfYT~Te(*dg;t`k@8pYV(|%~f1LXuG3V`6mib_!|V_1Mx(%b@QF>RB}B^PLA2$4HzgFiMs-Z^SHE!H4Gg?A1p3p>Y1ss(RM1S;X#BdN_|Q;)P(sF(f`zQG;wTx^+u?Bg!)IwUa(1rR~9axWbvt%>=t1k*-LecE}HO#Y=yVjd5gVm{s4*i!n^")))
    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%Wi`(5WFMt4|8b)jT3>?N)<}_BWVsi46N$di7_Po``R%Lq^U2Mnep!I*tJ#%l;5URa(&EoE(8}S>2Orq;HY!i@Gz*INKjF(J5!Om@eMa+n`>r;BuyO#WyNa<C7az_VpqCHHG(7sNp3&Jo|aJzsTvYl7{IPkVNfuX*dp=pxh27ojv}`TOO8#Wc!H_6%m%OT84AtwuZeNhO1vOVu(X<$)p$~K(`$)xv^OZKkXKdYToAjOx!jxdZU~z#<jhjFqdk^eTxNFMKj9fGnni-HKlt+h4DSVhM<;wBnf2;iVb^fpYc=(n4c6UqH;^s_7dpdf+S(}%L(edT!I?~ZXR21(RwX$;fk?)gkH^NCGG8M8UwVpXj?Hhs3F;rA;SsV|YO?WNMT;j<eaZ#9MmWUw8r`OkXL>F=?k)D-;$X=i3Q@g&")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
code = """
# 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.vector cimport vector
cdef extern from "/opt/atcoder-stl/atcoder/fenwicktree.hpp" namespace "atcoder":
    cdef cppclass fenwick_tree[T]:
        fenwick_tree(int n)
        void add(int p, T x)
        T sum(int l, int r)

cdef class FenwickTree:
    cdef fenwick_tree[long long] *_thisptr
    def __cinit__(self, int n):
        self._thisptr = new fenwick_tree[long long](n)
    cpdef void add(self, int p, long long x):
        self._thisptr.add(p, x)
    cpdef long long sum(self, int l, int r):
        return self._thisptr.sum(l, r)
"""
import os,sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
  
import sys
from atcoder import FenwickTree

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


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

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

    def add(self, idx, x):
        # add x to idx-th element
        # idx: 1-indexed
        self.data[idx] += x
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

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


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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline


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

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

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

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

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

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


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


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

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