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: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self, a):
        self.padding = 0
        self.n = len(a)
        self.N = 2 ** (self.n-1).bit_length()
        self.seg_data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        for i in range(2*self.N-2, 0, -2):
            self.seg_data[(i-1)//2] = self.seg_data[i] + self.seg_data[i-1]
    
    def __len__(self):
        return self.n
    
    def update(self, i, x):
        idx = self.N - 1 + i
        self.seg_data[idx] += x
        while idx:
            idx = (idx-1) // 2
            self.seg_data[idx] = self.seg_data[2*idx+1] + self.seg_data[2*idx+2]
    
    def query(self, i, j):
        # [i, j)
        if i == j:
            return self.seg_data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j # 閉区間にする
            result = self.padding
            while idx1 < idx2 + 1:
                if idx1&1 == 0: # idx1が偶数
                    result = result + self.seg_data[idx1]
                if idx2&1 == 1: # idx2が奇数
                    result = result + self.seg_data[idx2]
                    idx2 -= 1
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            return result
    
    @property
    def data(self):
        return self.seg_data[self.N-1:self.N-1+self.n]

N, Q = map(int, input().split())
A = list(map(int, input().split()))
st = SegmentTree(A)
ans = []
for _ in range(Q):
    t, i, j = map(int, input().split())
    if t:
        ans.append(st.query(i, j))
    else:
        st.update(i, j)

print(*ans, sep='\n')

Submission status: Time Limit Exceeded

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

class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r): #これで[l,r)から取り出す。
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)


N,Q = map(int,input().split())
A = list(map(int,input().split()))
Tree = SegmentTree(A, segfunc, 0)
for _ in range(Q):
  query, a,b = map(int,input().split())
  if query == 0:
    Tree.add(a,b)
  else:
    print(Tree.sum(a,b))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, Q = map(int, input().split())
a = list(map(int, input().split()))
a = np.array(a)
s = np.cumsum(a)
s = np.insert(s, 0, 0)

for _ in range(Q):
    t, x, y = map(int, input().split())

    if(t == 0):
        s[(x+1):] += y
    else:
        print(s[y]-s[x])

Submission status: Time Limit Exceeded

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

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

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

class BinaryIndexedTree:
    # 初期化処理
    def __init__(self, size):
        self.size = size
        self.dat = [0]*(size+1)

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.dat[i] += x
            i += i & -i # 更新すべき位置

    def sum(self, r):
        r += 1
        ret = 0
        while r>0:
            ret += self.dat[r]
            r -= r & -r # 加算すべき位置
        return ret

    def init(self, a):
        for i, x in enumerate(a):
            self.add(i, x)

    def initrng(self, a):
        self.add(0, a[0])
        for i in range(1,n):
            self.add(i, a[i]-a[i-1])

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

bit = BinaryIndexedTree(n)

bit.init(a)
ret = [bit.sum(i) for i in range(n)]
for _ in range(q):
    t, u, v = map(int, input().split())
    if t == 0:
        bit.add(u, v)
    else:
        print(bit.sum(v-1)-bit.sum(u-1))

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
lst = [int(i) for i in input().split()]
sum_list = [0]
total = 0
for i in range(n):
  total += lst[i]
  sum_list.append(total)
for _ in range(q):
  t, a, b = map(int, input().split())
  if t == 0:
    for i in range(a + 1, n + 1):
      sum_list[i] += b
  else:
    print(sum_list[b] - sum_list[a])

Submission status: Time Limit Exceeded

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

# Segment Tree
# 一点更新・範囲集約
# 1-indexed
# update(i,x)   :ai を x に変更する
# add(i,x)      :ai に x を加算する
# query(l,r)    :半開区間 [l,r) に対してモノイド al・…・ar−1 を返す
# モノイドとは、集合と二項演算の組で、結合法則と単位元の存在するもの
# ex. +, max, min
# [ 1] a0 ・ a1  ・ a2 ・ a3 ・ a4 ・ a5 ・ a6 ・ a7  ->[0]
# [ 2] a0 ・ a1  ・ a2 ・ a3       [ 3] a4 ・ a5 ・ a6・ a7
# [ 4] a0 ・ a1    [ 5] a2 ・ a3   [ 6] a4 ・ a5   [ 7] a6 ・ a7
# [ 8] a0 [ 9] a1  [10] a2 [11] a3 [12] a4 [13] a5 [14] a6 [15] a7

#                      [0001]
#          [0010]                  [0011]
#    [0100]      [0101]      [0110]      [0111]
# [1000][1001][1010][1011][1100][1101][1110][1111]

# size = 8  元の配列数の２べき乗値
# 親のインデックス         i//2 or i>>=1 bitで一個右シフト
# 左側の子のインデックス    2*i
# 右側の子のインデックス    2*i+1
# aiの値が代入されているインデックス    i+size

class SegmentTree:
    # 初期化処理
    # f     : SegmentTreeにのせるモノイド
    # idele : fに対する単位元
    def __init__(self, size, f=lambda x,y : min(x, y), idele=float('inf')):
        self.size = 2**(size-1).bit_length()    # 簡単のため要素数nを2冪にする
        self.idele = idele                      # 単位元
        self.f = f                              # モノイド
        self.dat = [self.idele]*(self.size*2)   # 要素を単位元で初期化

## one point
    def update(self, i, x):
        i += self.size  # 1番下の層におけるインデックス
        self.dat[i] = x
        while i > 0:    # 層をのぼりながら値を更新
            i >>= 1     # 1つ上の層のインデックス(完全二分木における親)
            # 下の層2つの演算結果の代入(完全二分木における子同士の演算)
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])
## one point
    def add(self, i, x):
        i += self.size  # 1番下の層におけるインデックス
        self.dat[i] += x
        while i > 0:    # 層をのぼりながら値を更新 indexが0になれば終了
            i >>= 1     # 1つ上の層のインデックス(完全二分木における親)
            # 下の層2つの演算結果の代入(完全二分木における子同士の演算)
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])
## range
    def query(self, l, r):
        l += self.size  # 1番下の層におけるインデックス
        r += self.size  # 1番下の層におけるインデックス
        lres, rres = self.idele, self.idele # 左側の答えと右側の答えを初期化
        while l < r:    # lとrが重なるまで上記の判定を用いて加算を実行
            # 左が子同士の右側(lが奇数)(lの末桁=1)ならば、dat[l]を加算
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1
            # 右が子同士の右側(rが奇数)(rの末桁=1)ならば、dat[r-1]を加算
            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres) # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res

    def init(self, a):
        for i, x in enumerate(a):
            # 1番下の層におけるインデックス
            self.dat[i + self.size] = x
        for i in range(self.size-1, -1, -1):
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

n, q = map(int, input().split())
a = list(map(int, input().split()))
sgt = SegmentTree(n, lambda x,y : x+y, 0)
sgt.init(a)
for _ in range(q):
    t, u, v = map(int, input().split())
    if t == 0:
        sgt.add(u, v)
    else:
        print(sgt.query(u, v))

Submission status: Time Limit Exceeded

Solution code:
n, q = list(map(lambda x: int(x), input().split()))
list_a = list(map(lambda x: int(x), input().split()))

# element of ith index is the sum of subarray: list_a[:i+1]
current_sum = 0
sum_list_a = []
for ele in list_a:
#     print(ele, current_sum)
    current_sum += ele
    sum_list_a.append(current_sum)

for _ in range(q):
    i, x, y = list(map(lambda x: int(x), input().split()))
    if i == 0:
        for i in range(x, n):
            sum_list_a[i] += y
        continue
        
    if (x == 0):
        print(sum_list_a[y-1])
        continue
    print(sum_list_a[y-1] - sum_list_a[x-1])

Submission status: Time Limit Exceeded

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):
    self.bit = [0] * n

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

  def sum_sub(self, i):
    a = 0
    i += 1
    while i:
      a += self.bit[i-1]
      i -= i & -i
    return a

  def sum(self, i, j):
    a = 0
    if j != 0:
      a += self.sum_sub(j-1)
    if i != 0:
      a -= self.sum_sub(i-1)
    return a

n,q=nii()
a=lnii()
Bit=BIT(n)
for i in range(n):
  Bit.add(i,a[i])
for i in range(q):
  t,a,b=map(int,input().split())
  if t==0:
    Bit.add(a,b)
  else:
    print(Bit.sum(a,b))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3


def main():
    n, q = list(map(int, input().split()))
    a = list(map(int, input().split()))

    for i in range(q):
        x, y, z = list(map(int, input().split()))

        if x == 1:
            print(sum(a[y:z]))
        elif x == 0:
            a[y] += z


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n, q = list(map(lambda x: int(x), input().split()))
list_a = list(map(lambda x: int(x), input().split()))

for _ in range(q):
    i, x, y = list(map(lambda x: int(x), input().split()))
    if i == 0:
        list_a[x] += y
        continue
    print(sum(list_a[x:y]))

Submission status: Time Limit Exceeded

Solution code:
# test
class BIT:
  ini = 0
  def __init__(s, num):
    s.N = 1
    while s.N <= num:
      s.N *= 2
    s.T = [s.ini] * s.N
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, n): # xにnを加える
    k = x + 1
    s.T[k - 1] += n
    k += k & -k
    while k <= s.N:
      s.T[k - 1] += n
      k += k & -k
  def getV(s, x): # xまでの和(x含む)
    if x < 0: return 0
    x += 1
    ans = s.T[x - 1]
    x -= x & -x
    while x != 0:
      ans += s.T[x - 1]
      x -= x & -x
    return ans

N, Q = list(map(int, input().split()))
a = list(map(int, input().split()))
Query = [list(map(int, input().split())) for _ in range(Q)]
  
bit = BIT(N)
bit.set(a)

for q in Query:
  if q[0] == 0:
    _, p, x = q
    bit.update(p, x)
  else:
    _, l, r = q
    print(bit.getV(r - 1) - bit.getV(l - 1))

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
ans = list(map(int, input().split()))
data = [0]*(n+1)
for _ in range(q):
    a, b, c = map(int, input().split())
    if a == 0:
        ans[b] += c
    else:
        print(sum(ans[b:c]))

Submission status: Time Limit Exceeded

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

def init(init_val):
    #set_val                                                                    
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built                                                                      
    for i in range(num-2,-1,-1):
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
    
def update(k,x):
    k+=num-1
    seg[k]=x
    while k+1:
        k=(k-1)//2
        seg[k]=segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p+=num-1
    q+=num-2
    res=ide_ele
    while q-p>1:
        if p&1==0:
            res=segfunc(res,seg[p])
        if q&1==1:
            res=segfunc(res,seg[q])
            q-=1
        p=p//2
        q=(q-1)//2
    if p==q:
        res=segfunc(res,seg[p])
    else:
        res=segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele=0
n,q=map(int,input().split())
num=2**(n-1).bit_length()
seg=[ide_ele]*2*num
a=list(map(int,input().split()))
init(a)
ans=0
for i in range(q):
    x,l,r=map(int,input().split())
    if x==0:
        update(l,query(l,l+1)+r)
    else:
        print(query(l,r))

Submission status: Time Limit Exceeded

Solution code:
class fenwick_tree:
    def __init__(self, n):
        self.data = [0 for _ in range(n+1)]
        self.n = n

    def add(self, p, x):
        p += 1
        while p <= self.n:
            self.data[p-1] += x
            p += p & -p
    
    def sum(self, l, r):
        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
    
N, Q = [int(_) for _ in input().split()]

fw = fenwick_tree(N)
A = [int(_) for _ in input().split()]
for i, a in enumerate(A):
    fw.add(i, a)

for i in range(Q):
    t, *q = [int(_) for _ in input().split()]
    if t == 0:
        p, x = q
        fw.add(p, x)
    else:
        l, r = q
        print(fw.sum(l, r))

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split(" "))
ar = list(map(int,input().split(" ")))
for i in range(q):
    a,x,y = map(int,input().split(" "))
    if a == 0:
        ar[x] += y
    else:
        print(sum(ar[x:y]))

Submission status: Time Limit Exceeded

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

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

for i in range(q):
  b, c, d = map(int, input().split())
  if b == 0:
    a[c] = a[c] + d
  else:
    e = sum(a[c:d])
    print(e)

Submission status: Time Limit Exceeded

Solution code:
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),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:print(g(r)-g(l))
  else:f(l+1,r)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
A = list(map(int, input().split()))
que = [list(map(int, input().split())) for _ in range(Q)]

for a, b, c in que:
    if a:
        print(sum(A[b:c]))
    else:
        A[b] += c

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
# import time,random,resource

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)
def IF(c, t, f): return t if c else f


class Seg():
    def __init__(self, na, default, func):
        if isinstance(na, list):
            n = len(na)
        else:
            n = na
        i = 1
        while 2**i <= n:
            i += 1
        self.D = default
        self.H = i
        self.N = 2**i
        if isinstance(na, list):
            self.A = [default] * (self.N) + na + [default] * (self.N-n)
            for i in range(self.N-1,0,-1):
                self.A[i] = func(self.A[i*2], self.A[i*2+1])
        else:
            self.A = [default] * (self.N*2)
        self.F = func

    def find(self, i):
        return self.A[i + self.N]

    def update(self, i, x):
        i += self.N
        self.A[i] = x
        while i > 1:
            i = i // 2
            self.A[i] = self.merge(self.A[i*2], self.A[i*2+1])

    def merge(self, a, b):
        return self.F(a, b)

    def total(self):
        return self.A[1]

    def query(self, a, b):
        A = self.A
        l = a + self.N
        r = b + self.N
        res = self.D
        while l < r:
            if l % 2 == 1:
                res = self.merge(res, A[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res = self.merge(res, A[r])
            l >>= 1
            r >>= 1

        return res


def main():
    n,q = LI()
    a = LI()
    qa = [LI() for _ in range(q)]

    def f(a, b):
        return a + b

    seg = Seg(a, 0, f)
    r = []
    for t,u,v in qa:
        if t == 0:
            c = seg.find(u)
            seg.update(u, c+v)
        else:
            r.append(seg.query(u,v))

    return JA(r, "\n")


print(main())

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    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 query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
      
N,Q=map(int,input().split())
*A,=map(int,input().split())
bit = BIT(N)
for i in range(N):
  bit.add(i+1,A[i])
for i in range(Q):
  q,a,b = map(int,input().split())
  if q:
    print(bit.query(a,b))
  else:
    bit.add(a+1,b)

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [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.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def subtract(self, i, x):
        self.add(i, -x)
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    
    def lower_bound(self, x):#和がx以上になる最小のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) >= x:
                r = index
            else:
                l = index
                
        if self.sum(l) >= x:
            return l
        return r
    
    def upper_bound(self, x):#和がx以下になる最大のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) <= x:
                l = index
            else:
                r = index
                
        if self.sum(r) <= x:
            return r
        return l
    

def main():
    n, q = map(int, input().split())
    bit = BIT(n)
    a = list(map(int, input().split()))
    for i, v in enumerate(a):
        bit.add(i+1, v)

    for i in range(q):
        query = list(map(int, input().split()))
        if query[0] == 0:
            p, x = query[1:]
            bit.add(p+1, x)
        else:
            l, r = query[1:]
            res = bit.get_sum(l, r)
            print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class fenwick_tree():
    n=1
    data=[0 for i in range(n)]
    def __init__(self,N):
        self.n=N
        self.data=[0 for i in range(N)]
    def add(self,p,x):
        assert 0<=p<self.n,"0<=p<n,p={0},n={1}".format(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 and l<=r and r<=self.n),"0<=l<=r<=n,l={0},r={1},n={2}".format(l,r,self.n)
        return self.sum0(r)-self.sum0(l)
    def sum0(self,r):
        s=0
        while(r>0):
            s+=self.data[r-1]
            r-=r&-r
        return s

N,Q=map(int,input().split())
a=[int(i) for i in input().split()]
FT=fenwick_tree(N)
for i in range(N):
    FT.add(i,a[i])
for i in range(Q):
    t,a,b=map(int,input().split())
    if t==0:
        FT.add(a,b)
    else:
        print(FT.sum(a,b))

Submission status: Time Limit Exceeded

Solution code:
'''
Created on 2020/09/08

@author: harurun
'''
# from dataclasses import *
# @dataclass
# class BIT:
#     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):
#         # assert i > 0
#         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)
def main():
  from itertools import accumulate
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  
  N,Q=map(int,pin().split())
  a=list(map(int,pin().split()))
  A=list(accumulate(a))
  for i in range(Q):
    t,p,x=map(int,pin().split())
    if t==0:
      a[p]+=x
      A=list(accumulate(a))
    else:
      if p==0:
        print(A[x-1])
      else:
        print(A[x-1]-A[p-1])
  return 
main()

Submission status: Time Limit Exceeded

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

for _ in range(Q):
  querry = list(map(int, input().split()))
  if querry[0] == 0:
    a[querry[1]] += querry[2]
  else:
    print(sum(a[querry[1]:querry[2]]))

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree: #1-indexed
    def __init__(self,list,f=lambda x,y:x+y,inf=0):
        self.height=(len(list)-1).bit_length()+1 #木の高さ
        self.id=inf #単位元
        self.tree=[self.id]*(2**self.height) #木を単位元で初期化
        self.f=f
        for i in range(len(list)):
            self.tree[2**(self.height-1)+i]=list[i]
        for i in range(2**(self.height-1)-1,0,-1):
            self.tree[i]=self.f(self.tree[2*i],self.tree[2*i+1])
        
    def update(self,i,x): #i番目の要素をxに変更
        i+=2**(self.height-1)
        self.tree[i]+=x
        while i>1:
            i//=2
            self.tree[i]=self.f(self.tree[2*i],self.tree[2*i+1])
    
    def query(self,l,r):
        l+=2**(self.height-1)
        r+=2**(self.height-1)
        lf,rf=self.id,self.id
        while l<r:
            if l&1:
                lf=self.f(lf,self.tree[l])
                l+=1
            if r&1:
                r-=1
                rf=self.f(self.tree[r],rf)
            l//=2
            r//=2
        return self.f(lf,rf)

n,q=map(int,input().split())
x=list(map(int,input().split()))
S=SegmentTree(x)
for i in range(q):
    a,b,c=map(int,input().split())
    if a==0:
        S.update(b,c)
    else:
        print(S.query(b,c))

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
ips = lambda:input().split()
import collections
import math
import itertools
import heapq as hq
import sys
input=sys.stdin.readline
class FenwickTree():
    def __init__(self,n):
        self.n = n
        self.tree = [0]*(n+1)
    def add(self,idx,a):#値の更新
        idx+=1
        while idx<=self.n:
            self.tree[idx] +=a
            idx += idx &-idx

    def _sum(self,r):
        ret=0
        r+=1
        while r>0:
            ret+=self.tree[r]
            r-=r&-r
        return ret
    def sum(self,l,r):
        return self._sum(r)-self._sum(l-1)

n,q = ma()
A = lma()
ft = FenwickTree(n)
for i in range(n):
    ft.add(i,A[i])
for i in range(q):
    t,u,v = ma()
    if t==0:
        ft.add(u,v)
    else:
        print(ft.sum(u,v-1))

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
ips = lambda:input().split()
import collections
import math
import itertools
import heapq as hq

class FenwickTree():
    def __init__(self,n):
        self.n = n
        self.tree = [0]*(n+1)
    def add(self,idx,a):#値の更新
        idx+=1
        while idx<=self.n:
            self.tree[idx] +=a
            idx += idx &-idx

    def _sum(self,r):
        ret=0
        r+=1
        while r>0:
            ret+=self.tree[r]
            r-=r&-r
        return ret
    def sum(self,l,r):
        return self._sum(r)-self._sum(l-1)

n,q = ma()
A = lma()
ft = FenwickTree(n)
for i in range(n):
    ft.add(i,A[i])
for i in range(q):
    t,u,v = ma()
    if t==0:
        ft.add(u,v)
    else:
        print(ft.sum(u,v-1))

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
A = list(map(int, input().split()))
seglen = 1
while seglen <= 2*n:
    seglen *= 2
offset = seglen//2
tree = [0] * seglen

def add(idx, x):
    idx += offset
    tree[idx] += x
    while idx > 1:
        idx //= 2
        tree[idx] = tree[2*idx] + tree[2*idx+1]

def sum_range(l, r):
    l += offset
    r += offset
    ret = 0
    while l < r:
        if l%2 == 1:
            ret += tree[l]
            l += 1
        l //= 2

        if r%2 == 1:
            ret += tree[r-1]
            r -= 1
        r //= 2
    return ret

for idx, a in enumerate(A):
    add(idx, a)

for _ in range(q):
    t, x, y = map(int, input().split())
    if t == 0:
        add(x, y)
    else:
        print(sum_range(x, y))

Submission status: Accepted

Solution code:
class BIT:
  def __init__(s, n):
    s._n = n
    s.data = [0] * n
  def set(s, L):
    for i in range(len(L)):
      s.add(i, L[i])
  def add(s, p, x):
    p += 1
    while p <= s._n:
      s.data[p - 1] += x
      p += p & -p
  def sum(s, l, r):
    return s.zum(r) - s.zum(l)
  def zum(s, r):
    ans = 0
    while r > 0:
      ans += s.data[r - 1]
      r -= r & -r
    return ans

N, Q = list(map(int, input().split()))
a = list(map(int, input().split()))
Query = [list(map(int, input().split())) for _ in range(Q)]
  
bit = BIT(N)
bit.set(a)
 
for q in Query:
  if q[0] == 0:
    _, p, x = q
    bit.add(p, x)
  else:
    _, l, r = q
    print(bit.zum(r) - bit.zum(l))

Submission status: Accepted

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

N, Q = list(map(int, input().split()))
a = list(map(int, input().split()))
Query = [list(map(int, input().split())) for _ in range(Q)]
  
bit = BIT(N)
for i in range(N):
  bit.add(i, a[i])
 
for q in Query:
  if q[0] == 0:
    _, p, x = q
    bit.add(p, x)
  else:
    _, l, r = q
    print(bit.zum(r) - bit.zum(l))

Submission status: Accepted

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

N, Q = list(map(int, input().split()))
a = list(map(int, input().split()))
Query = [list(map(int, input().split())) for _ in range(Q)]
  
bit = BIT(N)
for i in range(N):
  bit.add(i, a[i])
 
for q in Query:
  if q[0] == 0:
    _, p, x = q
    bit.add(p, x)
  else:
    _, l, r = q
    print(bit.sum(l, r))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
    
    def make(self, list):
        self.tree[1:] = list.copy()
        for i in range(self.size+1):
            j = i + (i & (-i))
            if j < self.size+1:
                self.tree[j] += self.tree[i]
 
    def sum(self, i):
        # [0, i) の要素の総和を返す
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s
    # 0 index を 1 index に変更  転倒数を求めるなら1を足していく
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    # 総和がx以上になる位置のindex をbinary search
    def bsearch(self,x):
        le = 0
        ri = 1<<(self.size.bit_length()-1)
        while ri > 0:
            if le+ri <= self.size and self.tree[le+ri]<x:
                x -= self.tree[le+ri]
                le += ri
            ri >>= 1
        return le+1

n,q = map(int,input().split())
a = list(map(int,input().split()))
bit = BIT(n)
bit.make(a)
for i in range(q):
    t,l,r = map(int,input().split())
    if t == 0:
        bit.add(l,r)
    else:
        print(bit.sum(r)-bit.sum(l))

Submission status: Accepted

Solution code:
class binaryindexedtree():
  def __init__(self,n):
    self.n=n
    self.tree=[0]*n
  def add(self,a,w):
    x=a
    while x<=self.n:
      self.tree[x-1]+=w
      x+=x&(-x)
  def sums(self,a):
    x=a
    S=0
    while x!=0:
      S+=self.tree[x-1]
      x-=x&(-x)
    return S
n,q=map(int,input().split())
a=list(map(int,input().split()))
bit=binaryindexedtree(n)
for i,x in enumerate(a,1):
  bit.add(i,x)
ans=[]
for _ in range(q):
  x,y,z=map(int,input().split())
  if x:ans+=[bit.sums(z)-bit.sums(y)]
  else:bit.add(y+1,z)
print(*ans,sep='\n')