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:
#https://juppy.hatenablog.com/entry/2018/11/17/%E8%9F%BB%E6%9C%AC_python_Binary_Indexed_Tree_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
n, Q = map(int, input().split())
#A1 ... AnのBIT(1-indexed)
BIT = [0]*(n+1)

#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
  

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

for i, x in enumerate(a):
  BIT_update(i+1, x)
  
for _ in range(Q):
  t, a, b = map(int, input().split())
  if t == 0:
    BIT_update(a+1, b)
  else:
    print(BIT_query(b)-BIT_query(a))

Submission status: Accepted

Solution code:
def segfunc(x,y):return x+y
ide_ele=0
class segtree():
  def __init__(self,init_val,segfunc=segfunc,ide_ele=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):
    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):
    res=self.ide_ele
    l+=self.num
    r+=self.num+1
    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
n,q=map(int,input().split())
st=segtree(list(map(int,input().split())))
ans=[]
for _ in range(q):
  x,y,z=map(int,input().split())
  if x:ans+=[st.query(y,z-1)]
  else:st.update(y,z)
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.buffer.readline


class SegmentTree:
    ele = 0

    def func(self, a, b):
        return a + b

    # SEG木は1-index
    # Aに関しては0-index

    def __init__(self, n):  # Aは0-idx
        self.n = n
        self.num = 2 ** ((self.n - 1).bit_length())
        self.SEG = [self.ele] * (2 * self.num)

    def search(self, idx):
        return self.SEG[idx + self.num]

    def initialize(self, A):
        for i in range(self.n):
            self.SEG[i + self.num] = A[i]
        for i in range(self.num - 1, 0, -1):
            self.SEG[i] = self.func(self.SEG[2 * i], self.SEG[2 * i + 1])

    def update(self, idx, val):
        idx += self.num
        self.SEG[idx] += val
        idx //= 2
        while idx:
            self.SEG[idx] = self.func(self.SEG[2 * idx], self.SEG[2 * idx + 1])
            idx //= 2

    def query(self, left, right):
        # 開区間
        resleft = self.ele
        resright = self.ele
        left += self.num
        right += self.num
        while right - left > 0:
            if left % 2 == 1:
                resleft = self.func(resleft, self.SEG[left])
                left += 1
            if right % 2 == 1:
                right -= 1
                resright = self.func(resright, self.SEG[right])
            left //= 2
            right //= 2
        return self.func(resleft, resright)


n, q = map(int, input().split())
ST = SegmentTree(n)
ST.initialize(list(map(int, input().split())))
for _ in range(q):
    s, a, b = map(int, input().split())
    if s:
        print(ST.query(a, b))
    else:
        ST.update(a, b)

Submission status: Accepted

Solution code:
class SegmentTree:
    ele = 0

    def func(self, a, b):
        return a + b

    # SEG木は1-index
    # Aに関しては0-index

    def __init__(self, n):  # Aは0-idx
        self.n = n
        self.num = 2 ** ((self.n - 1).bit_length())
        self.SEG = [self.ele] * (2 * self.num)

    def search(self, idx):
        return self.SEG[idx + self.num]

    def initialize(self, A):
        for i in range(self.n):
            self.SEG[i + self.num] = A[i]
        for i in range(self.num - 1, 0, -1):
            self.SEG[i] = self.func(self.SEG[2 * i], self.SEG[2 * i + 1])

    def update(self, idx, val):
        idx += self.num
        self.SEG[idx] += val
        idx //= 2
        while idx:
            self.SEG[idx] = self.func(self.SEG[2 * idx], self.SEG[2 * idx + 1])
            idx //= 2

    def query(self, left, right):
        # 開区間
        resleft = self.ele
        resright = self.ele
        left += self.num
        right += self.num
        while right - left > 0:
            if left % 2 == 1:
                resleft = self.func(resleft, self.SEG[left])
                left += 1
            if right % 2 == 1:
                right -= 1
                resright = self.func(resright, self.SEG[right])
            left //= 2
            right //= 2
        return self.func(resleft, resright)


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

ST = SegmentTree(n)
ST.initialize(A)
for _ in range(q):
    s, a, b = map(int, input().split())
    if s:
        print(ST.query(a, b))
    else:
        ST.update(a, b)

Submission status: Accepted

Solution code:
import sys
from collections.abc import Iterable


def read():
    return sys.stdin.buffer.readline().rstrip()


class FenwickTree:
    def __init__(self, arg):
        if isinstance(arg, int):
            self._n = arg
            self._a = [0] * arg
        elif isinstance(arg, Iterable):
            a = list(arg)
            self._n = len(a)
            self._a = [0] * self._n
            self.set(a)

    def set(self, a):
        for i, ai in enumerate(a):
            self.add(i, ai)

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

    def update(self, i, x):
        self.add(i, x - self.sum(i, i + 1))

    def sum(self, l, r):
        return self._sum(r) - self._sum(l)

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


def main():
    n, q = map(int, read().split())
    fw = FenwickTree(map(int, read().split()))
    for _ in range(q):
        query = [int(i) for i in read().split()]
        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:
import sys


def read():
    return sys.stdin.buffer.readline().rstrip()


class FenwickTree:
    def __init__(self, n):
        self._n = n
        self._a = [0] * n

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

    def sum(self, l, r):
        return self._sum(r) - self._sum(l)

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


def main():
    n, q = map(int, read().split())
    fw = FenwickTree(n)
    for i, ai in enumerate(map(int, read().split())):
        fw.add(i, ai)
    for _ in range(q):
        query = [int(i) for i in read().split()]
        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:
class BIT:
  def __init__(self,n,li):
    self.n = n
    self.el = [0] + li
    self.data = [0]*(n+1)
    for i in range(1,n+1):
      self.data[i] = sum(self.el[i+1-(i&-i):i+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)
n,q = map(int,input().split())
a = list(map(int,input().split()))
bt = BIT(n,a)
for _ in range(q):
  i,j,k = map(int,input().split())
  if i == 0:
    bt.add(j+1,k)
  else:
    print(bt.get(j+1,k))

Submission status: Accepted

Solution code:
class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)
    
    def build(self, lst):
        self.value = lst
        for i, x in enumerate(lst):
            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)

import sys
input = sys.stdin.readline

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

Submission status: Accepted

Solution code:
class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)
    
    def build(self, lst):
        self.value = lst
        for i, x in enumerate(lst):
            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)
    
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))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,q=map(int,input().split())

BIT=[0]*n
def ADD(x,y):#A[x]+=y,1-origin
	while x<=n:
		BIT[x-1]+=y
		x+=x&(-x)
def SUM(l):#1からlまでの和
	ret=0
	while l>=1:
		ret+=BIT[l-1]
		l-=l&(-l)
	return ret

IN=list(map(int,input().split()))
for i in range(n):
	ADD(i+1,IN[i])

for i in range(q):
	t,a,b=map(int,input().split())
	if t==0:
		ADD(a+1,b)
	else:
		print(SUM(b)-SUM(a))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,q=map(int,input().split())

BIT=[0]*n
def ADD(x,y):#A[x]+=y,1-origin
	while x<=n:
		BIT[x-1]+=y
		x+=x&(-x)
def SUM(l):#1からlまでの和
	if l==0:
		return 0
	ret=0
	while l>=1:
		ret+=BIT[l-1]
		l-=l&(-l)
	return ret

IN=list(map(int,input().split()))
for i in range(n):
	ADD(i+1,IN[i])

for i in range(q):
	t,a,b=map(int,input().split())
	if t==0:
		ADD(a+1,b)
	else:
		print(SUM(b)-SUM(a))

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
a=list(map(int,input().split()))
size=2*n+1
bit=[0]*size
def bit_update(x,v):
    while x<size:
        bit[x]+=v
        x+=(x&-x)
def bit_sum(n):
    s=0
    if n==0:return 0
    x=n
    while x>0:
        s+=bit[x]
        x-=(x&-x)
    return s
for i,j in enumerate(a,1):
    bit_update(i,j)
for i in range(q):
    a,b,c=map(int,input().split())
    if a==0:
        bit_update(b+1,c)
    else:
        print(bit_sum(c)-bit_sum(b))

Submission status: Accepted

Solution code:
class FenwickTree:
    def __init__(self, n, init_list=None):
        self.n = n
        self.data = [0] * n
        if init_list:
            assert n == len(init_list)
            for i in range(n):
                self.add(i, init_list[i])
        
    def add(self, i, val):
        assert 0 <= i < self.n
        i += 1
        while i <= self.n:
            self.data[i - 1] += val
            i += i & -i #LSBを加算して上の層へ
            
    def update(self, i, val):
        self.add(i, val - self.sum(i, i+1))

    def sum(self, l, r):
        assert  0 <= l <= r <= self.n
        if l != 0:
            return self.sum(0, r) - self.sum(0, l)
        ret = 0
        while r > 0:
            ret += self.data[r - 1]
            r -= r & -r #LSB減算して上の層へ
        return ret

n, q = map(int, input().split())
a = list(map(int, input().split()))
ft = FenwickTree(n, a)
ans = []
for _ in range(q):
    i, l, r = map(int, input().split())
    if i == 0:
        ft.add(l, r)
    else:
        ans.append(ft.sum(l, r))

for x in ans:
    print(x)

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 fenwick_tree():
    def __init__(self, n:int):
        self.__n = n
        self.__data = [0] * self.__n

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

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

    def __sum_mod0(self, r:int):
        s = 0
        while(r > 0):
            s += self.__data[r-1]
            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:
import sys


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


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


def range_sum(tree, l, r):
    return sum(tree, r) - sum(tree, l)


def main():
    n, q = map(int, sys.stdin.buffer.readline().split())

    bit = [0] + list(map(int, sys.stdin.buffer.readline().split()))
    for i in range(1, n+1):
        if i + (i & -i) < n + 1:
            bit[i + (i & -i)] += bit[i]

    for y in sys.stdin.buffer.readlines():
        q, p, x = map(int, y.split())
        if q:
            print(range_sum(bit, p, x))
        else:
            add(bit,n, p+1, x)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import types

_atcoder_code = """
# Python port of AtCoder Library.

__version__ = '0.0.1'
"""

atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)

_atcoder_fenwicktree_code = """
import typing


class FenwickTree:
    '''Reference: https://en.wikipedia.org/wiki/Fenwick_tree'''

    def __init__(self, n: int = 0) -> None:
        self._n = n
        self.data = [0] * n

    def add(self, p: int, x: typing.Any) -> None:
        assert 0 <= p < self._n

        p += 1
        while p <= self._n:
            self.data[p - 1] += x
            p += p & -p

    def sum(self, left: int, right: int) -> typing.Any:
        assert 0 <= left <= right <= self._n

        return self._sum(right) - self._sum(left)

    def _sum(self, r: int) -> typing.Any:
        s = 0
        while r > 0:
            s += self.data[r - 1]
            r -= r & -r

        return s
"""

atcoder.fenwicktree = types.ModuleType('atcoder.fenwicktree')
exec(_atcoder_fenwicktree_code, atcoder.fenwicktree.__dict__)
FenwickTree = atcoder.fenwicktree.FenwickTree

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

# from atcoder.fenwicktree import FenwickTree


def main() -> None:
    import sys

    n, q = map(int, sys.stdin.readline().split())
    fenwick_tree = FenwickTree(n)

    a = map(int, sys.stdin.readline().split())
    for i, ai in enumerate(a):
        fenwick_tree.add(i, ai)

    for _ in range(q):
        t, x, y = map(int, sys.stdin.readline().split())
        if t == 0:
            fenwick_tree.add(x, y)
        if t == 1:
            print(fenwick_tree.sum(x, y))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

#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

BIT=[0]*(N+1)
for i in range(N):
  BIT_update(i+1,alist[i])

for _ in range(Q):
  q1,q2,q3=map(int,input().split())
  if q1==0:
    BIT_update(q2+1,q3)
  else:
    print(BIT_query(q3)-BIT_query(q2))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, q = map(int,input().split())
A = list(map(int,input().split()))
C = [list(map(int,input().split())) for i in range(q)]

# ACLに伴い0-indexedに直した
class Bit:  # Fenwick Tree と同じ
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, l, r):  # [l,r)の合計を求める
        # 内部的には[l+1,r+1)の合計つまり(rまでの合計-lまでの合計)
        s = 0
        while r > 0:
            s += self.tree[r]
            r -= r & -r
        while l > 0:
            s -= self.tree[l]
            l -= l & -l
        return s
  
    def add(self, i, x):  # i番目にxを足す
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

# Bitの内部状態をindex順に出力
def print_bit(B):
    n = B.size
    ANS = []
    for i in range(n):
        ANS.append(B.sum(i, i+1))
    print(*ANS)

B = Bit(n)
for i in range(n):
    B.add(i, A[i])

for i in range(q):
    if C[i][0] == 0:
        B.add(C[i][1], C[i][2])
    else:
        print(B.sum(C[i][1], C[i][2]))

Submission status: Accepted

Solution code:
class Bit:
    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 (存在しない時は -1 ) , その時の a0+a1+...+ai )
        a0+a1+...+ai <= x としたい場合は equal = True
        二分探索であるため、ai>=0 を満たす必要がある
        """
        sum_ = 0
        pos = -1    # 1-indexed の時は pos = 0
        if not 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
        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
        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))

n,q = map(int,input().split())
a = list(map(int,input().split()))
B = Bit(n)
B.built(a)

for _ in range(q):
    a,b,c = map(int,input().split())
    if a == 0:
        B.add(b, c)
    else:
        print(B.get(b, c))

Submission status: Accepted

Solution code:
"""
n,q = map(int,input().split())
a = list(map(int,input().split()))

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

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
init(a)

for _ in range(q):
    q1,p,x = map(int,input().split())
    if q1 == 0:
        update(p, seg[p+num-1] + x)
    else:
        print(query(p, x))
"""



from typing import Callable, List, TypeVar

T = TypeVar("T")

class SegmentTree:
    """Segment Tree"""

    __slots__ = ["e", "op", "_n", "_size", "tree"]

    def __init__(self, a: List[T], e: T, op: Callable[[T, T], T]) -> None:
        self.e = e
        self.op = op
        self._n = len(a)
        self._size = 1 << (self._n - 1).bit_length()

        self.tree = [e] * self._size + a + [e] * (self._size - self._n)
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def _update(self, k: int) -> None:
        """Update the value of a[k]."""
        self.tree[k] = self.op(self.tree[2 * k], self.tree[2 * k + 1])

    def set(self, k: int, x: T) -> None:
        """Assign x to a[k] in O(log n)."""
        assert 0 <= k < self._n

        k += self._size
        self.tree[k] = x
        while k:
            k >>= 1
            self._update(k)

    def get(self, k: int) -> T:
        """Return a[k] in O(1)."""
        assert 0 <= k < self._n
        return self.tree[k + self._size]

    def prod(self, l: int, r: int) -> T:
        """Return op(a[l], ..., a[r - 1]). Return e, if l == r.
        Complexity: O(log n)
        """
        assert 0 <= l <= r <= self._n

        sml, smr = self.e, self.e
        l += self._size
        r += self._size

        while l < r:
            if l & 1:
                sml = self.op(sml, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.tree[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def prod_all(self) -> T:
        """Return op(a[0], ..., a[n - 1]. Return e if n == 0.
        Complexity: O(1)
        """
        return self.tree[1]

    def max_right(self, l: int, f: Callable[[T], bool]) -> int:
        """
        Return an index r satisfying both:
            1. r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. r = n or f(op(a[l], a[l + 1], ..., a[r])) = false.

        If f is monotone, this is the maximum r satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.

        Complexity: O(log n)
        """
        assert 0 <= l <= self._n
        assert f(self.e)

        if l == self._n:
            return self._n

        l += self._size
        sm = self.e

        while True:
            while not l & 1:
                l >>= 1

            if not f(self.op(sm, self.tree[l])):
                while l < self._size:
                    l *= 2
                    if f(self.op(sm, self.tree[l])):
                        sm = self.op(sm, self.tree[l])
                        l += 1
                return l - self._size

            sm = self.op(sm, self.tree[l])
            l += 1

            if (l & -l) == l:
                break

        return self._n

    def min_left(self, r: int, f: Callable[[T], bool]) -> int:
        """
        Return an index l satisfying both:
            1. l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. l = 0 or f(op(a[l - 1], a[l + 1], ..., a[r - 1])) = false.
        If f is monotone, this is the minimum l satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.

        Complexity: O(log n)
        """
        assert 0 <= r <= self._n
        assert f(self.e)

        if not r:
            return 0

        r += self._size
        sm = self.e

        while True:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1

            if not f(self.op(self.tree[r], sm)):
                while r < self._size:
                    r = 2 * r + 1
                    if f(self.op(self.tree[r], sm)):
                        sm = self.op(self.tree[r], sm)
                        r -= 1
                return r + 1 - self._size

            if (r & -r) == r:
                break

        return 0

def add(x, y):
    return x + y

n,q = map(int,input().split())
a = list(map(int,input().split()))
tree = SegmentTree(a, 0, add)

for _ in range(q):
    t,p,x = map(int,input().split())
    if t == 0:
        tree.set(p, tree.get(p) + x)
    else:
        print(tree.prod(p, x))

Submission status: Accepted

Solution code:
from numba import njit, b1, i4, i8, f8
import numpy as np
import sys


@njit((i8[:], i8), cache=True)
def sum(tree, i):
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & -i
    return s


@njit((i8[:], i8, i8, i8), cache=True)
def add(tree, size,  i, x):
    while i <= size:
        tree[i] += x
        i += i & -i


@njit((i8[:], i8, i8), cache=True)
def range_sum(tree, l, r):
    return sum(tree, r) - sum(tree, l)


def main():
    n, q = map(int, sys.stdin.buffer.readline().split())

    bit = np.array([0] + sys.stdin.buffer.readline().split(), np.int64)
    for i in range(1, n+1):
        if i + (i & -i) < n + 1:
            bit[i + (i & -i)] += bit[i]

    for y in sys.stdin.buffer.readlines():
        q, p, x = map(int, y.split())
        if q:
            print(range_sum(bit, p, x))
        else:
            add(bit, n, p+1, x)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys


class Bit:
    def __init__(self, n, arr):
        self.size = n
        self.tree = [0] + arr
        for i in range(1, n+1):
            if i + (i & -i) < n + 1:
                self.tree[i + (i & -i)] += self.tree[i]

    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 range_sum(self, l, r):
        return self.sum(r) - self.sum(l)


def main():
    n, q = map(int, sys.stdin.buffer.readline().split())
    bit = Bit(n, list(map(int, sys.stdin.buffer.readline().split())))
    for x in sys.stdin.buffer.readlines():
        q, p, x = map(int, x.split())
        if q:
            print(bit.range_sum(p, x))
        else:
            bit.add(p+1, x)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

class Bit:
    def __init__(self, n, arr):
        self.size = n
        self.tree = [0] + arr
        for i in range(1, n+1):
            x = i + (i & -i)
            if x < n + 1:
                self.tree[x] += self.tree[i]

    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 range_sum(self, l, r):
        return self.sum(r) - self.sum(l)


def main():
    n, q = map(int, sys.stdin.buffer.readline().split())
    bit = Bit(n, list(map(int, sys.stdin.buffer.readline().split())))
    for x in sys.stdin.buffer.readlines():
        q, p, x = map(int, x.split())
        if q:
            print(bit.range_sum(p, x))
        else:
            bit.add(p+1, x)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit, i8, jitclass
import sys

spec = [
    ("size", i8),
    ("tree", i8[:])
]


@jitclass(spec)
class Bit:
    def __init__(self, n, arr):
        self.size = n
        self.tree = np.array([0] + arr, np.int64)
        for i in range(1, n+1):
            x = i + (i & -i)
            if x < n + 1:
                self.tree[x] += self.tree[i]

    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 range_sum(self, l, r):
        return self.sum(r) - self.sum(l)


def main():
    n, q = map(int, sys.stdin.buffer.readline().split())
    bit = Bit(n, list(map(int, sys.stdin.buffer.readline().split())))
    for x in sys.stdin.buffer.readlines():
        q, p, x = map(int, x.split())
        if q:
            print(bit.range_sum(p, x))
        else:
            bit.add(p+1, x)


if __name__ == "__main__":
    main()