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:

code = """

# distutils: language=c++
# distutils: include_dirs=[/home/USERNAME/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False


cimport numpy as np
cdef extern from "<atcoder/fenwicktree>" namespace "atcoder" nogil:
    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, np.ndarray[long, ndim=1] array):
        cdef int N = array.size
        self._thisptr = new fenwick_tree[long long](N)
        for i in range(N):
            self.add(i, array[i])
    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, getpass

if sys.argv[-1] == 'ONLINE_JUDGE':
    code = code.replace("USERNAME", getpass.getuser())
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
    sys.exit(0)


from atcoder import FenwickTree
import numpy as np

N,Q = list(map(int,input().split()))
bit = FenwickTree(np.array(list(map(int,input().split())), dtype=np.int))

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

Submission status: Accepted

Solution code:
class BIT: #0-indexed
    __slots__ = ["size", "tree","depth","n0"]
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length()
        self.n0 = 1<<self.depth

    def get_sum(self, i): #a_0 + ... + a_{i} #閉区間
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def range_sum(self,l,r): #a_l + ... + a_r 閉区間
        return self.get_sum(r) - self.get_sum(l-1) 

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

    def bisect_left(self,w):
        #和が w 以上になる最小の index
        #w が存在しない場合 self.size を返す
        if w <= 0: return 0
        x,k = 0,self.n0
        for _ in range(self.depth):
            k >>= 1
            if x+k <= self.size and self.tree[x+k] < w:
                w -= self.tree[x+k]
                x += k
        return x
    
###########################################
import sys
readline = sys.stdin.readline

n,q = map(int, readline().split())
*a, = map(int, readline().split())

b = BIT(n)
for i in range(n):
    b.add(i,a[i])

for _ in range(q):
    v,p,x = map(int, readline().split())
    if v==0:
        b.add(p,x)
    else:
        print(b.range_sum(p,x-1))

Submission status: Accepted

Solution code:
class BIT: #0-indexed
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length()
        self.n0 = 1<<self.depth
#        self.element = [0]*(n+1)
    def get_sum(self, i): #a_0 + ... + a_{i} #閉区間
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def query(self,l,r): #a_l + ... + a_r 閉区間
        return self.get_sum(r) - self.get_sum(l-1) 
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        # self.element[i] += x
    #def get(self,i): return element[i]        
    def bisect_left(self,w):
        #和が w 以上になる最小の index
        #w が存在しない場合 self.size を返す
        if w <= 0: return 0
        x,k = 0,self.n0
        for _ in range(self.depth):
            k >>= 1
            if x+k <= self.size and self.tree[x+k] < w:
                w -= self.tree[x+k]
                x += k
        return x
    
###########################################
import sys
readline = sys.stdin.readline

n,q = map(int, readline().split())
*a, = map(int, readline().split())

b = BIT(n)
for i in range(n):
    b.add(i,a[i])

for _ in range(q):
    v,p,x = map(int, readline().split())
    if v==0:
        b.add(p,x)
    else:
        print(b.query(p,x-1))

Submission status: Accepted

Solution code:

code = """

# distutils: language=c++
# distutils: include_dirs=[/home/USERNAME/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False


cdef extern from "<atcoder/fenwicktree>" namespace "atcoder" nogil:
    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, getpass

if sys.argv[-1] == 'ONLINE_JUDGE':
    code.replace("USERNAME", getpass.getuser())
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
    sys.exit(0)


from atcoder import FenwickTree

import sys

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
bit = FenwickTree(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:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7
#main code here!
    n,q=MI()
    #ソース　https://juppy.hatenablog.com/entry/2018/11/17/蟻本_python_Binary_Indexed_Tree_競技プログラミング
    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)
    #idxの一番下のbit
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum
    
    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return
    lis=LI()
    for i in range(n):
        BIT_update(i+1,lis[i])
    for i in range(q):
        a,b,c=MI()
        if a==0:
            BIT_update(b+1,c)
        else:
            ans=BIT_query(c)-BIT_query(b)
            print(ans)



        
        
        
        
        
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
# Binary Indexed Tree (Fenwick Tree)
class BIT:
  def __init__(self, n):
    self.n = n
    self.bit = [0]*(n+1)
    self.el = [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):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.bit[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i-1)

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
A = list(map(int, input().split()))
bit = BIT(N)
for i in range(N):
  bit.add(i+1,A[i])
ans = []
for i in range(Q):
  t,a,b = map(int, input().split())
  if t:
    ans.append(bit.get(a+1,b))
  else:
    bit.add(a+1,b)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n+1)

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

    def add(self, i, x):  # i > 0
        assert i > 0
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


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

bit = Bit(N)

for i, v in enumerate(a):
    bit.add(i+1, v)

for i in range(Q):
    b, c, d = map(int, input().split())

    if b == 0:
        bit.add(c+1, d)
    else:
        print(bit.sum(d) - bit.sum(c))

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


cdef extern from "<atcoder/fenwicktree>" namespace "atcoder" nogil:
    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')


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:

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


cdef extern from "<atcoder/fenwicktree>" 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')


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:
# 1 - indexed
# 指定したindexに対してaddで数値を足す
# get(L,R)で、L～Rの累積和を求める（両端とも含む）
# 0を指定すると返ってこないので注意
class FenwickTree: # (BinaryIndexedTree)
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 1)
    self.el = [0] * (n + 1)
  
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  
  def add(self, i, x):
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i

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

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

FT = FenwickTree(N)

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

Submission status: Accepted

Solution code:
def main():
    N, Q = map( int, input().split())
    A = list( map( int, input().split()))
    bit = [0]*N
    def add(bit,a,w):#リストに値を追加する関数
        x = a
        while x <= N:
            bit[x-1] += w
            x += x&(-x)

    def sums(bit,a):#k番目までの和
        x = a
        S = 0
        while x > 0:
            S += bit[x-1]
            x -= x&(-x)
        return S

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

Submission status: Accepted

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

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

    def add(self, p, x):
        """ a[p] += xを行う"""
        assert 0 <= p and p < self.n
        p += 1
        while p <= self.n:
            self.data[p - 1] += x
            p += p & -p

    def sum(self, l, r):
        """a[l] + a[l+1] + .. + a[r-1]を返す"""
        assert 0 <= l and l <= r and r <= self.n
        return self.__sum(r) - self.__sum(l)


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

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

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

Submission status: Accepted

Solution code:
class Binary_Indexed_Tree_Exception(Exception):
    pass

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

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

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

        X=[None]+[unit]*k

        self.num=k
        self.depth=d

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

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

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

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

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

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

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

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

        a=self.index(k,index)
        if right==False:
            #左から
            y=self.calc(x,self.inv(a))
        else:
            #右から
            y=self.calc(self.inv(a),x)

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

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

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

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

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

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

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

Submission status: Accepted

Solution code:
import sys

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


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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

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


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

if __name__ == "__main__":
    main()

Submission status: Accepted

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


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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

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

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

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

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

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

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

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

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

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

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

Submission status: Accepted

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

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

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

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

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

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

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

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

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

ft = fenwick_tree(n)
ans = []

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

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

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

Submission status: Accepted

Solution code:
class BIT:
    """
    Binary Index Tree
    ###1-origin####

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

    #material http://hos.ac/slides/20140319_bit.pdf
    """

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

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

        return ret

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

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

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

        RETURN:
            res:index of x
        """
        k+=1 #convert k into 1-index

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

        i=N//2
        while i>0:
            if(res+i<self.size and self.L[res+i]<k): #move to rignt on tree
                k-=self.L[res+i]
                res+=i
            #else move to left
            i//=2
        return res+1

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

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

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

Submission status: Accepted

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

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

def main():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    BITTree = construct(a, len(a))
    for _ in range(q):
        i, j, k = map(int, input().split())
        if i:
            print(getsum(BITTree, k - 1) - getsum(BITTree, j - 1))
        else:
            updatebit(BITTree, len(a), j, k)
    # freq = [2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9] 
    # BITTree = construct(freq,len(freq)) 
    # print("Sum of elements in arr[0..5] is " + str(getsum(BITTree,5))) 
    # freq[3] += 6
    # updatebit(BITTree, len(freq), 3, 6) 
    # print("Sum of elements in arr[0..5]"+
    #                     " after update is " + str(getsum(BITTree,5))) 

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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


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

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

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

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


solve()

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

    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:
import sys
input = lambda: sys.stdin.readline()


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

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

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


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

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

Submission status: Accepted

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

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