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:
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(self.n+1) # 1-indexed
 
    def init(self, init_val):
        for i, v in enumerate(init_val):
            self.add(i, v)
 
    def add(self, i, x):
        # i: 0-indexed
        i += 1 # to 1-indexed
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)
 
    def sum(self, i, j):
        # return sum of [i, j)
        # i, j: 0-indexed
        return self._sum(j) - self._sum(i)
 
    def _sum(self, i):
        # return sum of [0, i)
        # i: 0-indexed
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & (-i)
        return res
 
    def lower_bound(self, x):
        s = 0
        pos = 0
        depth = self.n.bit_length()
        v = 1 << depth
        for i in range(depth, -1, -1):
            k = pos + v
            if k <= self.n and s + self.bit[k] < x:
                    s += self.bit[k]
                    pos += v
            v >>= 1
        return pos

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

bit = BIT(n)
bit.init(A)

for _ in range(q):
  i, j, k = map(int, input().split())
  if i == 0:
    bit.add(j, k)
  else:
    print(bit.sum(j, k))

Submission status: Accepted

Solution code:
import math


class BinaryIndexedTree():
    def __init__(self, N):
        self.N = N
        self.arr = [0] * (N+1)

    def query(self, i):
        ret = 0
        i += 1
        while i:
            ret += self.arr[i]
            lsb = i & (-i)
            i -= lsb
        return ret

    def add(self, i, v):
        i += 1
        while i < self.N+1:
            lsb = i & (-i)
            self.arr[i] += v
            i += lsb

    def search(self, x):
        pos = 0
        cur = 0
        idx = 2 ** int(math.log(self.N, 2))
        while idx >= 1:
            if pos + idx <= self.N and cur + self.arr[pos+idx] < x:
                cur += self.arr[pos+idx]
                pos += idx
            idx //= 2
        return pos


def main():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    bit = BinaryIndexedTree(N)
    for i, a in enumerate(A):
        bit.add(i, a)
    for _ in range(Q):
        qtype, a, b = map(int, input().split())
        if qtype == 0:
            bit.add(a, b)
        else:
            ans = bit.query(b-1) - bit.query(a-1)
            print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
S=sys.stdin.readlines()
def Binit(B,siz):
  while len(B)<siz+1:
    B.append(0)
  while len(B)>siz+1:
    del B[-1]
  for i in range(siz+1):
    B[i]=0
  B.append(siz)

def Badd(B,a,x):
  z=a
  while z<=B[-1]:
    B[z]+=x
    z+=(z&(-z))

def Bsum(B,a):
  r=0
  z=a
  while z>0:
    r+=B[z]
    z-=(z&(-z))
  return r

def Bssum(B,a,b):
  return Bsum(B,max(a,b))-Bsum(B,min(a,b)-1)

BIT=[]
N,Q=map(int,S[0].split())
Binit(BIT,N+1)
A=list(map(int,S[1].split()))
for i in range(N):
  Badd(BIT,i+1,A[i])
a,b,c=0,0,0
for i in range(Q):
  a,b,c=map(int,S[i+2].split())
  if a:
    print(Bssum(BIT,b+1,c))
  else:
    Badd(BIT,b+1,c)

Submission status: Accepted

Solution code:
from copy import *
import sys
S=sys.stdin.readlines()

def init(N,node,unit,func):
  n=1
  while n<N:
    n<<=1
  for i in range(n*2-1):
    if len(node)<=i:
      node.append(deepcopy(unit))
    else:
      node[i]=deepcopy(unit)
  node.append(func)
  node.append(unit)
  node.append(n)

def upd(node,x,a):
  y=node[-1]+x
  node[y-1]=a
  while y>1:
    y=y>>1
    node[y-1]=node[-3](node[(y<<1)-1],node[y<<1])

def query(node,l,r):
  x,y=l,r
  z=node[-1]-1
  r=node[-2]
  while True:
    if x==y:
      return r
    if x&1:
      r=node[-3](r,node[x+z])
      x+=1
    if y&1:
      r=node[-3](r,node[y+z-1])
    x>>=1
    y>>=1
    z>>=1
    if z==0:
      return r

def bis_min_k(node,k,cond):
  x=k+1
  while True:
    if node[-1]<=x:
      return x-node[-1]
    if cond(node[(x<<1)-1]):
      x=x<<1
    else:
      x=(x<<1)+1

def bis_min(node,l,r,cond):
  x,y=l,r
  z=node[-1]-1
  for i in range(30):
    if x+(1<<i)>y:
      break
    if x&(1<<i):
      if cond(node[z+(x>>i)]):
        return bis_min_k(node,z+(x>>i),cond)
      x+=(1<<i)
    if z==0:
      break
    z>>=1
  for i in range(29,-1,-1):
    if i and ((node[-1]-1)>>(i-1))==0:
      continue
    if x+(1<<i)>y:
      continue
    if (y-x)&(1<<i):
      if cond(node[((node[-1]-1)>>i)+(x>>i)]):
        return bis_min_k(node,((node[-1]-1)>>i)+(x>>i),cond)
      x+=(1<<i)
  return node[-1]

N,Q=map(int,S[0].split())
A=list(map(int,S[1].split()))
X=[]
init(N+1,X,0,lambda x,y:x+y)
for i in range(N):
  upd(X,i,A[i])
a,b,c=0,0,0
for i in range(Q):
  a,b,c=map(int,S[i+2].split())
  if a:
    print(query(X,b,c))
  else:
    upd(X,b,X[X[-1]+b-1]+c)

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

from libc.stdio cimport scanf, printf
cdef int n, q, i, a, t, u, v
scanf('%d%d', &n, &q)
cdef fenwick_tree[long] *bit = new fenwick_tree[long](n)
for i in range(n):
    scanf('%d', &a)
    bit.add(i, a)
for i in range(q):
    scanf('%d%d%d', &t, &u, &v)
    if t:
        printf('%ld\n', bit.sum(u, v))
    else:
        bit.add(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:
import sys
from random import *
from collections import *
from heapq import *

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij = [(1, 0), (-1, 0), (0, 1), (0, -1)]

# 内部で1-indexedに変えるので入力は0-indexedでよい
# i項目までの和（i含む）
class BitSum:
    def __init__(self, n):
        self.n = n+1
        self.table = [0]*self.n

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

    # [0,i]の和
    def sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.table[i]
            i -= i & -i
        return res

    # [l,r)の和
    def sumlr(self, l, r):
        if l == r: return 0
        if l == 0: return self.sum(r-1)
        return self.sum(r-1)-self.sum(l-1)

    # 数列を度数分布とみたときに、x番目がどのインデックスにあるかを返す
    # xが大きすぎるときは配列の長さnを返す
    def rank(self, x):
        idx = 0
        for lv in range((self.n-1).bit_length()-1, -1, -1):
            mid = idx+(1 << lv)
            if mid >= self.n: continue
            if self.table[mid] < x:
                x -= self.table[mid]
                idx += 1 << lv
        return idx

n,q=MI()
aa=LI()
bit=BitSum(n)
for i,a in enumerate(aa):bit.add(i,a)
for _ in range(q):
    t,a,b=MI()
    if t:print(bit.sumlr(a,b))
    else:bit.add(a,b)

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${@q!EWL(6ukQ@o>Y}4C6HEoS)r!K{Q_>gtH{_6Saob;JGAWA?{fmdfx-dH<9YLD;+H%Cmp*hsD!&3n^|qs1QL*`)JftU5Gu3fXbLo6l?o2C6W^@ofP#wypGK{KH$xUgGVQ2J@<<HW~AQqOg4;1vJ?pk}q8Yjw=7B*l#c?BEOY3|t$$<;5aydaG;EubD-`rxGA0+X#ZE<h_<FT&)U<9a!#3e6PII3WmO;b;XH4Jd;eYXstkDe65mLVrs35s<hdfWQ7s>HxLA?AP$jX`rM>B2d>%Y8mP}O9a3R)f9cP&Ih$r!9oRZxW1q4Wg4Er%YVW&**ech{tzy+1-uk+hZ8$3YmJI}ibb1<+SDo+eZOzaCNATn%0`KtT*4oW<Ul#U6BT`~;VV(HFt6Zs+<xw)5(vIkXV(|%#P)9s3wZq-tG_0UUeLk}7M7%U;=A^aCp9cCapgqloIY8oW2wurU$R&EM126i*LSzq>+z|-T!nV<4lh?}W0p%~*GHZ(5UTJG)4Ch;WIFQFj1%t})o9M*YZ4kV4zVs^UjRkd1%v{+0uH37W>1g&kv|nML&|KQ4<%{ZjSLtmK{B0_#yF6u3=TgM5gF2rl2MQjV~X|5I5pUr-W2Yy3(s!Q<P2TT4ugnnAS9F3r$f5pe>AdVi+D*f*6HOC_}#b^oIUge@*mdeY(o")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
"""うしくん元気ですか
# distutils: language=c++
# distutils: include_dirs=/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include
# cython: boundschack=False
cimport numpy as np
from libc.stdio cimport scanf, printf
import numpy as np

cdef class BIT:
    cdef int n
    cdef np.ndarray data

    def __cinit__(BIT self, int n):
        self.n = n
        self.data = np.zeros(n + 1, np.int_)

    cdef void add(BIT self, int i, long x):
        while i <= self.n:
            self.data[i] += x
            i += i & -i

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

def main():
    cdef int n, q, a, i, t, u, v
    scanf('%d%d', &n, &q)
    cdef BIT bit = BIT(n)
    for i in range(n):
        scanf('%d', &a)
        bit.add(i + 1, a)
    for i in range(q):
        scanf('%d%d%d', &t, &u, &v)
        if t:
            printf('%ld\n', bit.sum(v) - bit.sum(u))
        else:
            bit.add(u + 1, v)
main()
"""

import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${rhO^=%}5WVv&Mp|ta6ariIQbnbQ9xC<TTU#N=Hp!@FOl*^G`s+J}BtSMk;WzU>>@iQE(1$*t@mny0_PyBaO0L(*)4YNtO|NvV(D|x7*jAU)QqVpK3T0ue6s9z|E4y<zSo&CeDm@0h>4f~lg1)4_?as_`y1ZzyfgGB*u(LfWFAv;YeG|s(L}J@n7hs@)@IYPCINJhy$ifGO7Op*B3Tkrb98zeK2gF1w-GDU0d-(eO$2I|81I7%XX-i!}N;oIZphOVKP>F@QmPi=tI%Ph1ZP;(%W}{eK5iJO+i{K54N)hdff7)4}60G4v9`~$JXUSxLvZz2Pb!UP(7)yJ2o0<JRpwWQvxw`mHrG@cN{0-|0-WFAi5W)&JICCF7eBa)?&s=AHe4^KPX}-YgU5@B94|A7ebIWnXoDRJs@JSNAT7i^i_XEq}n1jgU#e^LC98N>S@D9?KXZ5UJa#(TO>X=Q`c&r@;4$faGjg`haPJjfCpT15P^SsJMF_GPH)+pkTaGaxfD0F-zbWO&gSDbovnnbaIu)MnQIWx_uU&O3v8>e&1U~}8_*(9O)zgbFLllEg$wj1v=`44!$7r+")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())

A=[0]+list(map(int,input().split()))

LEN=N+1
BIT=[0]*(LEN+1) # 1-indexedなtree

def update(v,w): # index vにwを加える
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v)) # 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v): # [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) # 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS

for i in range(1,N+1):
    update(i,A[i])

for i in range(Q):
    q,p,x=map(int,input().split())
    if q==0:
        p+=1
        update(p,x)
    else:
        l=p+1
        r=x+1

        print(getvalue(r-1)-getvalue(l-1))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

### BIT binary
def init(bit, values):
    for i,v in enumerate(values):
        add(bit,i+1,v)
#a1 ~ aiまでの和 O(logn)
def query(bit,i):
    res = 0
    while i > 0:
        res += bit[i]
        i -= i&(-i)
    return res

#ai += x(logN)
def add(bit,i,x):
    if i==0:
        raise RuntimeError
    while i <= len(bit)-1:
        bit[i] += x
        i += i&(-i)
    return

def index(bit, v):
    """a1,...,aiの和がv以上になる最小のindexを求める
    存在しないとき配列サイズを返す
    """
    i = 0
    n = len(bit)-1
    k = 1<<((n-1).bit_length())
    while k>0:
        if i+k<n+1 and bit[i+k]<v:
            v -= bit[i+k]
            i += k
        k //= 2
    if v==1:
        return i+1
    else:
        return n+1
bit = [0]*(n+1)    
init(bit, list(map(int, input().split())))
for i in range(q):
    t,u,v = map(int, input().split())
    if t==0:
        add(bit, u+1, v)
    else:
        print(query(bit, v) - query(bit, u))

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self,len_A):
        self.N = len_A + 10
        self.bit = [0]*(len_A+10)
        
    def query(self,i):
        res = 0
        idx = i+1
        while idx:
            res += self.bit[idx]
            idx -= idx&(-idx)
        return res

    def update(self,i,x):
        idx = i+1
        while idx < self.N:
            self.bit[idx] += x
            idx += idx&(-idx)
    
    def lower_left(self,w):
        if (w < 0):
            return -1
        x = 0
        k = 1<<(self.N.bit_length()-1)
        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
    
n, q = map(int, input().split())
a = list(map(int, input().split()))
bit = BIT(n)
for i in range(n):
    bit.update(i, a[i])

for i in range(q):
    x, y, z = map(int, input().split())
    if x == 0:
        bit.update(y, z)
    else:
        print(bit.query(z-1) - bit.query(y-1))

Submission status: Accepted

Solution code:
class BIT():

    __slots__ = ["n", "data"]

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

    def point_append(self, index, delta):
        index += 1
        while index < self.n:
            self.data[index] += delta
            index += index & -index
        
    def prefix_folded(self, end):
        res = 0
        while end: # 変更箇所
            res += self.data[end]
            end -= end & -end
        return res

    def folded(self, begin, end):
        ret = 0
        while begin < end:
            ret += self.data[end]
            end -= end & -end
        while end < begin:
            ret -= self.data[begin]
            begin -= begin & -begin
        return ret

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

    N, Q = map(int, input().split())
    bit = BIT(list(map(int, input().split())))
    ans = []
    for _ in range(Q):
        a, b, c = map(int, input().split())
        if a:
            ans.append(bit.folded(b, c))
        else:
            bit.point_append(b, c)

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class BIT():

    __slots__ = ["n", "data"]

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

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

    def folded(self, begin, end):
        ret = 0
        while begin < end:
            ret += self.data[end]
            end -= end & -end
        while end < begin:
            ret -= self.data[begin]
            begin -= begin & -begin
        return ret

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

    N, Q = map(int, input().split())
    bit = BIT(list(map(int, input().split())))
    ans = []
    for _ in range(Q):
        a, b, c = map(int, input().split())
        if a:
            ans.append(bit.folded(b, c))
        else:
            bit.point_append(b, c)

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:


def lowbit(x):
	return x & (-x)

def update(n , c ,x , y):
	while x <= n:
		c[x] += y
		x += lowbit(x)

def query(c , x):
	ans = 0
	while x != 0:
		ans += c[x]
		x -= lowbit(x)
	return ans

def main():
	n , q = map(int , input().split())
	a_li = list(map(int , input().split()))
	a_li.insert(0,0)
	sum_li = [0 for _ in range(n + 1)]
	for i in range(1 , n + 1):
		sum_li[i] = sum_li[i - 1] + a_li[i]

	c = [0 for _ in range(n + 1)]
	for _ in range(q):
		t , l , r = map(int , input().split())
		if t == 1:
			print(query(c , r) - query(c , l) +  sum_li[r] - sum_li[l])
		else:
			update(n , c , l + 1 , r)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))


class BIT():
    def __init__(self,init_value):
        self.n = len(init_value)
        self.tree = [0]*(self.n+1)
        for i in range(1,self.n+1):
            x = init_value[i-1]
            while i <= self.n:
                self.tree[i] += x
                i += i & (-i)
    def update(self,i,x):  # i(1-index)番目の値を+x
        while i <= self.n:
            self.tree[i] += x
            i += i & (-i)
        return
    def query(self,i):  # 1番目からi(1-index)番目までの和を返す
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & (-i)
        return res


N,Q = MI()
A = LI()
BIT = BIT(A)
for _ in range(Q):
    p,q,r = MI()
    if p == 0:
        BIT.update(q+1,r)
    else:
        print(BIT.query(r)-BIT.query(q))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
a = list(map(int, input().split()))

class FenwickTree:
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 2)
  def sum(self, l, r):
    s = 0
    while l > 0:
      s -= self.data[l]
      l -= l & -l
    while r > 0:
      s += self.data[r]
      r -= r & -r
    return s
  def add(self, i, x):
    i += 1
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def lowerbound(self, s):
    x = 0
    y = 0
    for i in range(self.n.bit_length(), -1, -1):
      k = x + (1 << i)
      if k <= self.n and (y + self.data[k] < s):
        y += self.data[k]
        x += 1 << i
    return x + 1
fwk = FenwickTree(N)
for x in range(N): fwk.add(x, a[x])
for _ in range(Q):
  q, x, y = map(int, input().split())
  if q: print(fwk.sum(x, y))
  else: fwk.add(x, y)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
a = list(map(int, input().split()))

class FenwickTree:
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 2)
  def sum(self, i):
    i += 1
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    i += 1
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def lowerbound(self, s):
    x = 0
    y = 0
    for i in range(self.n.bit_length(), -1, -1):
      k = x + (1 << i)
      if k <= self.n and (y + self.data[k] < s):
        y += self.data[k]
        x += 1 << i
    return x + 1
fwk = FenwickTree(N)
for x in range(N): fwk.add(x, a[x])
for _ in range(Q):
  q, x, y = map(int, input().split())
  if q: print(fwk.sum(y - 1) - fwk.sum(x - 1))
  else: fwk.add(x, y)

Submission status: Accepted

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

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def build(self, lis):
        self.value = lis
        for i, x in enumerate(lis):
            self.add(i+1, x)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)


def main():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    
    bit = FenwickTree(n)
    bit.build(a)
    
    for i in range(q):
        a, b, c = map(int, input().split())
        if a == 0:
            bit.add(b+1, c)
        else:
            print(bit.get_sum(b, c))
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def build(self, lis):
        self.value = lis
        for i, x in enumerate(lis):
            self.add(i+1, x)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)


def main():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    
    bit = FenwickTree(n)
    bit.build(a)
    
    for i in range(q):
        a, b, c = map(int, input().split())
        if a == 0:
            bit.add(b+1, c)
        else:
            print(bit.get_sum(b, c))
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def build(self, lis):
        self.value = lis
        for i, x in enumerate(lis):
            self.add(i+1, x)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)


def main():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    
    bit = FenwickTree(n)
    bit.build(a)
    
    for i in range(q):
        query = list(map(int, input().split()))
        if query[0] == 0:
            bit.add(query[1]+1, query[2])
        else:
            print(bit.get_sum(query[1], query[2]))
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.bit = [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):
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    


def main():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    
    bit = FenwickTree(n)
    for i, x in enumerate(a):
        bit.add(i+1, x)
    
    for i in range(q):
        query = list(map(int, input().split()))
        if query[0] == 0:
            bit.add(query[1]+1, query[2])
        else:
            print(bit.get_sum(query[1], query[2]))
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
      
class BIT:
    #1-indexed
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.p = 2**(n.bit_length() - 1)
        self.dep = n.bit_length()
    def get(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 bl(self, v):
        if v <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < v:
                s += k
                v -= self.tree[s+k]
            k //= 2
        return s + 1
  
N, Q = map(int, readline().split())

T = BIT(N+1)
A = [0] + list(map(int, readline().split()))

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

Ans = []
for _ in range(Q):
    t, a, b = map(int, readline().split())
    if t == 0:
        T.add(a+2, b)
    else:
        Ans.append(T.get(b+1) - T.get(a+1))

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

Submission status: Accepted

Solution code:
def main():
  def f(i,x):
    while i<=n:
      b[i]+=x
      i+=i&-i
  def g(i):
    s=0
    while i:
      s+=b[i]
      i-=i&-i
    return s
  (n,q,*w),a,*t=[[*map(int,t.split())]for t in open(0)]
  b=[0]*-~n
  *map(f,range(1,n+1),a),
  for q,l,r in t:
    if q:w+=g(r)-g(l),
    else:f(l+1,r)
  print(' '.join(map(str,w)))
main()

Submission status: Accepted

Solution code:
def main():
  def f(i,x):
    while i<=n:
      b[i]+=x
      i+=i&-i
  def g(i):
    s=0
    while i:
      s+=b[i]
      i-=i&-i
    return s
  (n,q,*w),a,*t=[map(int,t.split())for t in open(0)]
  b=[0]*-~n
  *map(f,range(1,n+1),a),
  for q,l,r in t:
    if q:w+=g(r)-g(l),
    else:f(l+1,r)
  print(' '.join(map(str,w)))
main()

Submission status: Accepted

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

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

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

from sys import stdin
abc=[list(map(int,stdin.readline().split()))for _ in range(Q)]

for a,b,c in abc:
    if a:print(bit.sum(c)-bit.sum(b))
    else:bit.add(b+1,c)

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


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

    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 lower_bound(self, w):
            if w <= 0:
                return 0
            x = 0
            k = 1 << (self.size.bit_length() - 1)
            while k:
                if x + k <= self.size and self.tree[x + k] < w:
                    w -= self.tree[x + k]
                    x += k
                k >>= 1
            return x + 1

    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    bit = Bit(N)
    for i, a in enumerate(A):
        bit.add(i+1, a)
    for _ in range(Q):
        q, x, y = map(int, input().split())
        if q == 0:
            bit.add(x+1, y)
        else:
            print(bit.sum(y) - bit.sum(x))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

abc=[list(map(int,input().split()))for _ in range(Q)]

for a,b,c in abc:
    if a:print(bit.sum(c)-bit.sum(b))
    else:bit.add(b+1,c)

Submission status: Accepted

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

    def query(self,idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        while idx <= self.num:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return

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.update(i+1,a[i])

for i in range(Q):
    q,l,r = map(int,input().split())
    if q == 0:
        bit.update(l+1,r)
    else:
        res = bit.query(r) - bit.query(l)
        print(res)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class BinaryIndexTree:
    def __init__(self, n):
        self.size = n
        self._container = [0] * (n + 1)
        self.depth = n.bit_length()

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

    def add(self, i, x):
        if i == 0:
            return
        while i <= self.size:
            self._container[i] += x
            i += i & (-i)

    def lower_bound(self, x):
        if x == 0:
            return 0

        s = 0
        idx = 0
        for i in range(self.depth, -1, -1):
            k = idx + (1 << i)
            if k <= self.size and s + self._container[k] < x:
                s += self._container[k]
                idx += 1 << i
        return idx + 1

    def __repr__(self):
        return str(self._container)


def main():
    N, Q = map(int, readline().split())
    a = list(map(int, readline().split()))
    bit = BinaryIndexTree(N + 1)

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

    for _ in range(Q):
        a, b, c = map(int, readline().split())
        if a == 0:
            b += 1
            bit.add(b, c)
        else:
            b += 1
            c += 1
            print(bit.sum(c - 1) - bit.sum(b - 1))


if __name__ == '__main__':
    main()