Problem:


Range Sum Query

Write a program which manipulates a sequence A = {a1, a2, . . . , an} with the following operations:

add(i, x): add x to ai.

getSum(s, t): print the sum of as, as+1,...,at.

Note that the initial values of ai (i = 1, 2, . . . , n) are 0.

Input

n q
com1 x1 y1
com2 x2 y2
...
comq xq yq

In the first line, n (the number of elements in A) and q (the number of queries) are given. Then, q queries are given where com represents the type of queries. '0' denotes add(xi, yi) and '1' denotes getSum(xi, yi).

Output

For each getSum operation, print the sum in a line.

Constraints

1 ≤ n ≤ 100000

1 ≤ q ≤ 100000

If comi is 0, then 1 ≤ xi ≤ n, 0 ≤ yi ≤ 1000.

If comi is 1, then 1 ≤ xi ≤ n, 1 ≤ yi ≤ n.

Sample Input 1

3 5
0 1 1
0 2 2
0 3 3
1 1 2
1 2 2

Sample Output 1

3
2



Sample input:
3 5
0 1 1
0 2 2
0 3 3
1 1 2
1 2 2


Sample output:
3
2

Submission status: Accepted

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

class SegmentTree():
    def __init__(self,arr,func=min,ie=2**63):
        self.n = 2**(len(arr)-1).bit_length()
        self.ie = ie
        self.func = func
        self.tree = [ie for _ in range(2*self.n)]
        for i in range(len(arr)):
            self.tree[self.n+i-1] = arr[i]
        for i in range(self.n-1)[::-1]:
            self.tree[i] = func(self.tree[2*i+1],self.tree[2*i+2])
    def update(self,index,x):
        index += self.n-1
        self.tree[index] = x
        while index>0:
            index = (index-1)//2
            self.tree[index] = self.func(self.tree[2*index+1],self.tree[2*index+2])
    def query(self,left,right): #開区間！
        if right <= left:
            return self.ie
        left += self.n-1
        right += self.n-2
        res = self.ie
        while right-left > 1:
            if left & 1 == 0:
                res = self.func(res,self.tree[left])
            if right & 1 == 1:
                res = self.func(res,self.tree[right])
                right -= 1
            left = left//2
            right = (right-1)//2
        if left == right:
            res = self.func(res,self.tree[left])
        else:
            res = self.func(self.func(res,self.tree[left]),self.tree[right])
        return res

N,Q = map(int,input().split())
A = [0 for _ in range(N)]

st = SegmentTree(A,lambda x,y:x+y,0)
ans = []

for _ in range(Q):
    com,x,y = map(int,input().split())
    if com == 0:
        st.update(x-1,st.query(x-1,x)+y)
    else:
        ans.append(st.query(x-1,y))

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

Submission status: Accepted

Solution code:
class Segment_Tree:
    def __init__(self,n,func,init):
        self.n = n
        self.tree = [init]*(2*self.n - 1)
        self.func = func
        self.init = init

    def update(self,i,x):
        i += self.n - 1
        self.tree[i] = x
        while i>0:
            i = int((i-1)/2)
            self.tree[i] = self.func((self.tree[2*i+1], self.tree[2*i+2]))

    def find(self,a,b,k,l,r):
        if r <= a or b <= l:
            return self.init
        if a <= l and r <= b:
            return self.tree[k]
        vl = self.find(a,b,k*2+1,l,int((l+r)/2))
        vr = self.find(a,b,k*2+2,int((l+r)/2),r)
        return self.func((vl, vr))

n, q = map(int, input().split())
N = 1
while N < n:
    N *= 2

func = lambda a: a[0]+a[1]

segtre = Segment_Tree(N,func,0)

for _ in range(q):
    com, x, y = map(int, input().split())
    if com == 0: #add
        segtre.update(x-1,segtre.tree[x + segtre.n - 2]+y)
    else: #getSum
        print(segtre.find(x-1,y,0,0,N))

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, array, seg_func, ide_ele):
        n = len(array)
        self.size = 2**(n - 1).bit_length()
        self.seg_func = seg_func
        self.ide_ele = ide_ele
        self.seg = [self.ide_ele] * (2 * self.size - 1)

        for i in range(n):
            self.seg[i + self.size - 1] = array[i]
        for i in range(self.size - 2, -1, -1):
            self.seg[i] = self.seg_func(self.seg[2 * i + 1], self.seg[2 * i + 2])

    def update(self, index, sbn):
        index += self.size - 1
        self.seg[index] += sbn
        while index:
            index = (index - 1) // 2
            self.seg[index] = self.seg_func(self.seg[index * 2 + 1], self.seg[index * 2 + 2])

    def query(self, lower_ep, upper_ep):
        if upper_ep <= lower_ep:
            return self.ide_ele
        lower_ep += self.size - 1
        upper_ep += self.size - 2
        res = self.ide_ele
        while (upper_ep - lower_ep) > 1:
            if lower_ep & 1 == 0:
                res = self.seg_func(res, self.seg[lower_ep])
            if upper_ep & 1 == 1:
                res = self.seg_func(res, self.seg[upper_ep])
                upper_ep -= 1

            lower_ep //= 2
            upper_ep = (upper_ep - 1) // 2
        if lower_ep == upper_ep:
            res = self.seg_func(res, self.seg[lower_ep])
        else:
            res = self.seg_func(self.seg_func(res, self.seg[lower_ep]), self.seg[upper_ep])
        return res


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


n, q = map(int, input().split())
seg = SegmentTree([0] * n, add, 0)
for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        seg.update(x - 1, y)
    else:
        print(seg.query(x - 1, y))

Submission status: Accepted

Solution code:
n,q = map(int,input().split(" "))
tree = [0] * (n + 1)
querys = [tuple(map(int,input().split(" "))) for _ in range(q) ]

def b_sum(i):

    ans = 0
    while i > 0:
        ans += tree[i]
        i -=(i) & (-i)


    return ans



for query in querys:
    com,x,y = query
    if com == 0:
        i = x
        x = y

        while i <= n:

            tree[i] += x
            i += (i) & (-i)

    if com == 1:

        s = x - 1
        t = y




        print(b_sum(t) - b_sum(s))

Submission status: Accepted

Solution code:
class FenwickTree:
    """FenwickTree (Binary Indexed Tree, 0-index)

    Queries:
        1. add(i, val): add val to i-th value
        2. sum(n): sum(bit[0] + ... + bit[n-1])

    complexity: O(log n)

    See: http://hos.ac/slides/20140319_bit.pdf
    """

    def __init__(self, a_list):
        self.N = len(a_list)
        self.bit = a_list[:]
        for _ in range(self.N, 1 << (self.N - 1).bit_length()):
            self.bit.append(0)
        for i in range(self.N-1):
            self.bit[i | (i+1)] += self.bit[i]

    def add(self, i, val):
        while i < self.N:
            self.bit[i] += val
            i |= i + 1

    def sum(self, n):
        ret = 0
        while n >= 0:
            ret += self.bit[n]
            n = (n & (n + 1)) - 1
        return ret

    def query(self, low, high):
        return self.sum(high) - self.sum(low)


def yosupo():
    # https://judge.yosupo.jp/problem/point_add_range_sum
    N, Q = map(int, input().split())
    fwt = FenwickTree([int(x) for x in input().split()])
    for _ in range(Q):
        type_, l, r = map(int, input().split())
        print([fwt.sum(i) for i in range(N+1)])
        if type_ == 0:
            fwt.add(l, r)
        else:
            print(fwt.query(l, r))


def aoj():
    # https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_B
    N, Q = map(int, input().split())
    fwt = FenwickTree([0] * N)
    for _ in range(Q):
        type_, l, r = map(int, input().split())
        if type_ == 0:
            fwt.add(l-1, r)
        else:
            print(fwt.query(l-2, r-1))


if __name__ == "__main__":
    # yosupo()
    aoj()

Submission status: Accepted

Solution code:
class Bit(object):
    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N + 1)

    def add(self, a: int, w: int):
        x: int = a
        while x <= self.N:
            self.bit[x] += w
            x += x & -x

    def sum(self, a: int):
        ret: int = 0
        x: int = a
        while x > 0:
            ret += self.bit[x]
            x -= x & -x

        return ret

    def range_sum(self, x, y):
        ret1 = self.sum(y)
        ret2 = self.sum(x - 1)

        return ret1 - ret2


N, q = input().split()
N = int(N)
q = int(q)
bit = Bit(N)

for _ in range(q):
    mode, x, y = input().rstrip().split()
    if mode == "0":
        bit.add(int(x), int(y))
    else:
        ret = bit.range_sum(int(x), int(y))
        print(ret)

Submission status: Accepted

Solution code:
def add(bit, a, w, n):
    x = a
    while x <= n:
        bit[x] += w
        x += x & -x


def sum_from_zero(bit, a):
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & -x
    return ret


def main():
    [n, q] = [int(num) for num in input().split()]

    bit = [0 for _ in range(n + 1)]

    for i in range(q):
        [com, x, y] = [int(num) for num in input().split()]

        if com == 0:
            add(bit, x, y, n)
        else:
            print(sum_from_zero(bit, y) - sum_from_zero(bit, x-1))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, q = [int(s) for s in input().split()]
bit = [0] * (n+1)

def add(a, w):
    x = a
    while x <= n:
        bit[x] += w
        x += (x & -x)


def sum(a):
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= (x & -x)
    return ret


for _ in range(q):
    com, x_i, y_i = [int(s) for s in input().split()]
    if com == 0:
        add(x_i,y_i)
        
    else:
        ans = sum(y_i) - sum(x_i-1)
        print(ans)

Submission status: Accepted

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

class SegmentTree:
    def __init__(self, n): #a1, a2, ..., an
        n_ = 1
        while n_ < n:
            n_ *= 2

        self.n = n_
        self.arr = [0] * (2*self.n-1)

    def update(self, k, a): #0_indexed
        k += self.n - 1
        self.arr[k] += a

        while k > 0:
            k = (k-1) // 2
            self.arr[k] = func(self.arr[2*k+1], self.arr[2*k+2])

    def query(self, l, r):#[l,r)の値を返す
        L, R = l+self.n, r+self.n
        res = 0
         #ex) 最小値のセグ木 → +inf
         #　和のセグ木 → 0
         #　積のセグ木 → 1
         #  gcdのセグ木 → 0

        while L < R:
            if R & 1:
                R -= 1
                res = func(res, self.arr[R-1])

            if L & 1:
                res = func(res, self.arr[L-1])
                L += 1

            L >>= 1
            R >>= 1

        return res
#0-indexedな気がする
n,q=map(int,input().split())
sg=SegmentTree(n)
for _ in range(q):
    c,x,y=map(int,input().split())
    if c==0:
        sg.update(x-1,y)
    else:
        print(sg.query(x-1,y))

Submission status: Accepted

Solution code:
#min query から初期化を0にしてminを+に変えただけ
#minquery の方は0-indexだったがこっちは1-index
n,q = map(int,input().split( ))
s = 1
while s < n:
    s*=2

A = [0]*(2*s-1)

def query(a,b,k,l,r):#区間[a,b)について[l,r)を担当するkが答える
    if r<=a or b<=l:#はみ出る
        return 0
    if a<=l and r<=b:#含まれる
        return A[k]
    else:#ノード追うのが大変,##+1,+2
        c1 = query(a,b,2*k+1,l,(l+r)//2)    
        c2 = query(a,b,2*k+2,(l+r)//2,r)
        return c1+c2

for _ in range(q):
    c,x,y = map(int, input().split( ))
    if not c:
        x += (s-1)###-1
        x -=1###
        A[x] += y
        while x>0:
            x =(x-1)//2
            A[x] = A[x*2+1]+A[x*2+2]##+1,+2
        #print(A)
            
    else:
        print(query(x-1,y,0,0,s))
        #pass

Submission status: Accepted

Solution code:
class Binary_Indexed_Tree:

    def __init__(self,n):
        self.size=n
        self.graph=[0]*(n+1)

    def partially_sum(self,i):
        res=0
        while i>0:
            res+=self.graph[i]
            i-=i&-i
        return res

    def add_element(self,i,x):
        while self.size>=i:
            self.graph[i]+=x
            i+=i&-i

n,q=map(int,input().split())
tree=Binary_Indexed_Tree(n)
for _ in range(q):
    c,x,y=map(int,input().split())
    if c==0:
        tree.add_element(x,y)
    else:
        print(tree.partially_sum(y)-tree.partially_sum(x-1))

Submission status: Accepted

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

class SegmentTree:
    def __init__(self, num, ide_ele=0):
        tmp = 1
        while tmp < num:
            tmp *= 2
        self.n = tmp
        self.ide_ele = ide_ele
        self.l = [ide_ele] * (2 * self.n - 1)
    
    def func(self, x, y):
        return x + y
        # return min(x, y)

    def update(self, i, val):
        i = self.n - 1 + i
        self.l[i] += val
        while i > 0:
            i = (i-1)//2
            self.l[i] = self.func(self.l[i*2+1], self.l[i*2+2])
    
    def query(self, a, b, k, l, r):
        # print(a, b, k, l, r)
        if r <= a or b <= l:
            return self.ide_ele
        if a <= l and r <= b:
            return self.l[k]
        vl = self.query(a, b, k*2+1, l, (l+r)//2)
        vr = self.query(a, b, k*2+2, (l+r)//2, r)
        return self.func(vl, vr)

def main():
    N, Q = map(int, input().split())

    segt = SegmentTree(N)

    for _ in range(Q):
        c, x, y = map(int, input().split())
        if c == 0:
            segt.update(x-1, y)
        else:
            print(segt.query(x-1, y, 0, 0, segt.n))
        # print(segt.l)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n, q = map(int, input().split())
    nums = [0] * (n+1)
    
    for i in range(q):
        com, x, y = map(int, input().split())
        
        if not com:
            while x <= n:
                nums[x] += y
                x += x & -x
        else:
            x -= 1
            s_sum = 0
            while x:
                s_sum += nums[x]
                x -= x & -x
            t_sum = 0
            while y:
                t_sum += nums[y]
                y -= y & -y
                
            print(t_sum - s_sum)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class BIT():
	def __init__(self, n):
		self.n = n
		self.bit = [0]*(n+1)
	
	def getsum(self, k):
		ret = 0
		while k:
			ret += self.bit[k]
			k -= k&-k
		return ret
		
	def p_sum(self, i, j):
		return self.getsum(j)-self.getsum(i-1)
		
	def add(self, k, x):
		while k <= n:
			self.bit[k] += x
			k += k&-k

n,q = map(int,input().split())
BIT = BIT(n)
for _ in range(q):
	c,x,y = map(int,input().split())
	if c==0:
		BIT.add(x,y)
	else:
		print(BIT.p_sum(x,y))

Submission status: Accepted

Solution code:
class BIT:
  def __init__(self, size):
    self.tree = [0] * (size + 1)
    self.size = size
  
  def sum(self, a):
    res = 0
    a += 1
    while a:
      res += self.tree[a]
      a -= a & -a
    return res
  def add(self, a, x):
    a += 1
    while a < len(self.tree):
      self.tree[a] += x
      a += a & -a

import sys

stdin = sys.stdin
na = lambda: map(int, stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())

def main():
  n, q = na()
  bit = BIT(n)
  for _ in range(q):
    t, x, y = na()
    if t == 0:
      bit.add(x - 1, y)
    else:
      print(bit.sum(y - 1) - bit.sum(x - 2))

main()

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

class Rsum():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [0 for _ in range(2*self.n-1)]

	def Access(self, x):
		return self.node[x+self.n-1]

	def Add(self, x, val):
		x += self.n-1
		self.node[x] += val
		while x > 0:
			x = (x-1)//2
			self.node[x] = self.node[2*x+1] + self.node[2*x+2]
		return

	#[a, b)
	def Get(self, a, b, k=0, l=0, r=-1):
		if r < 0:
			r = self.n

		if a >= r or b <= l:
			return 0
		elif a <= l and b >= r:
			return self.node[k]
		else:
			vl = self.Get(a, b, 2*k+1, l, (l+r)//2)
			vr = self.Get(a, b, 2*k+2, (l+r)//2, r)
			return vl + vr

n, q = map(int, input().split())
SegT = Rsum(n)
for _ in range(q):
	c, x, y = map(int, input().split())
	if c == 0:
		SegT.Add(x-1, y)
	else:
		print(SegT.Get(x-1, y))

Submission status: Accepted

Solution code:
class RSQ(object):
    INIT = 0

    def __init__(self, num) -> None:
        n = 1
        while n <= num:
            n = n * 2
        self.n = n
        self.val = [self.INIT] * (2 * n - 1)

    @staticmethod
    def merge(a: int, b: int) -> int:
        return a + b

    def update(self, k: int, x: int) -> None:
        k = k + self.n - 1
        self.val[k] += x
        while k:
            k = (k - 1) // 2
            self.val[k] = self.merge(self.val[k * 2 + 1], self.val[k * 2 + 2])

    def dfs(self, beg: int, end: int, k: int, l: int, r: int) -> int:
        if (end <= l or r <= beg):
            return self.INIT
        if (beg <= l and r <= end):
            return self.val[k]
        vl = self.dfs(beg, end, k * 2 + 1, l, (l + r) // 2)
        vr = self.dfs(beg, end, k * 2 + 2, (l + r) // 2, r)
        return self.merge(vl, vr)

    def query(self, beg: int, end: int) -> int:
        return self.dfs(beg, end, 0, 0, self.n)


if __name__ == "__main__":
    n, q = map(lambda x: int(x), input().split())
    rmq = RSQ(n)

    for _ in range(q):
        com, x, y = map(lambda x: int(x), input().split())
        if (0 == com):
            rmq.update(x, y)
        else:
            print(rmq.query(x, y + 1))

Submission status: Accepted

Solution code:
class SegmentTree():
    """一点加算、区間取得クエリをそれぞれO(logN)で答えるデータ構造を構築する
    add: i番目にvalを加える
    get_sum: 区間[begin, end)の和を求める
    """
    def __init__(self, n):
        self.n = n
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [0] * (2*self.size - 1)

    def add(self, i, val):
        i += (self.size - 1)
        self.node[i] += val
        while i > 0:
            i = (i - 1) // 2
            self.node[i] = self.node[2*i + 1] + self.node[2*i + 2]

    def get_sum(self, begin, end):
        begin += (self.size - 1)
        end += (self.size - 1)
        s = 0
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                s += self.node[end]
            if (begin - 1) & 1:
                s += self.node[begin]
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2
        return s

    def debug(self):
        """Segment Tree上の葉の配列を出力する"""
        return(self.node[self.size - 1: self.size - 1 + self.n])


n, q = map(int, input().split())
info = [list(map(int, input().split())) for i in range(q)]
st = SegmentTree(n)
 
for i in range(q):
    com, x, y = info[i]
    if com == 0:
        st.add(x - 1, y)
    else:
        print(st.get_sum(x - 1, y))

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
bit=[0]*(n+1)
def add(a,w):
    x=a
    while(x<=n):
        bit[x]+=w
        x+=x&(-x)
def sum(a):
    ret=0
    x=a
    while(x>0):
        ret+=bit[x]
        x-=x&(-x)
    return ret
for j in range(q):
    com,x,y=map(int,input().split())
    if com==0:
        add(x,y)
    else:
        print(sum(y)-sum(x-1))

Submission status: Accepted

Solution code:
class SegmentTree:
    
    def __init__(self, n):
        self.n = n
        self.T = [0 for _ in range(2*n-1)]
        
    def add(self, i, x):
        i += self.n - 1
        self.T[i] += x
        while(i > 0):
            i = (i - 1) // 2
            self.T[i] += x
            
    def get_sum(self, a, b, k, l, r):
        if r<= a or b<= l:
            return 0
        if a <= l and r <= b:
            return self.T[k]
        vl = self.get_sum(a, b, k*2+1, l,(l+r)//2)
        vr = self.get_sum(a, b, k*2+2, (l+r)//2,r)
        return vl + vr
    

n_, q = [int(i) for i in input().split()]
n = 1
while(n < n_):
    n *= 2
T = SegmentTree(n)
for _ in range(q):
    c, x, y = [int(i) for i in input().split()]
    if c == 0:
        T.add(x - 1, y)
    else:
        print(T.get_sum(x - 1, y, 0, 0, n))

Submission status: Accepted

Solution code:
line = input()
n, q = list(map(int, line.split()))
N = 1
while N < n + 1:
    N *= 2
a = [0 for _ in range(0, 2 * N - 1)]

def update(k, v):
    k += N - 1
    a[k] += v
    while k > 0:
        k = (k - 1) // 2
        a[k] = a[k * 2 + 1] + a[k * 2 + 2]

def query(x, y, k, l, r):
    if r <= x or y <= l:
        return 0
    elif x <= l and r <= y:
        return a[k]
    m = (l + r) // 2
    return query(x, y, k * 2 + 1, l, m) + query(x, y, k * 2 + 2, m, r)

for _ in range(0, q):
    line = input()
    c, x, y = list(map(int, line.split()))
    if c == 0:
        update(x, y)
    elif c == 1:
        ans = query(x, y + 1, 0, 0, N)
        print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from operator import add

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')

class SegTree:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_val: 区間[l, r)の値を得る
    """
 
    def __init__(self, n, func, init):
        """
        :param n: 要素数
        :param func: 値の操作に使う関数(min, max, addなど)
        :param init: 要素の初期値
        """
        self.n = n
        self.func = func
        self.init = init
        # nより大きい2の冪数
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.init] * (n2 << 1)
 
    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 1:
            self.tree[i >> 1] = x = self.func(x, self.tree[i ^ 1])
            i >>= 1
 
    def get_val(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        return self._get_val(a, b, 1, 0, self.n2)
 
    def _get_val(self, a, b, k, l, r):
        """
        [a, b)の値を得る内部関数
        :param k: 現在調べている区間のtree内index
        :param l, r: kが表す区間の左右端index [l, r)
        :return: kが表す区間と[a, b)の共通区間内での最小値。共通区間を持たない場合は初期値
        """
        # 範囲外なら初期値
        if r <= a or b <= l:
            return self.init
        # [a,b)が完全に[l,r)を包含するならtree[k]の値を採用
        if a <= l and r <= b:
            return self.tree[k]
        # 一部だけ範囲内なら2つに分けて再帰的に調査
        m = (l + r) // 2
        return self.func(
            self._get_val(a, b, k << 1, l, m),
            self._get_val(a, b, (k << 1) + 1, m, r)
        )

N,Q=MAP()
# 1-indexed対応
st=SegTree(N+1, add, 0)
for _ in range(Q):
    com,x,y=MAP()
    if com==0:
        st.update(x, y+st.get_val(x, x+1))
    else:
        print(st.get_val(x, y+1))

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, lst, op, e):
        self.n = len(lst)
        self.N = 2**((self.n-1).bit_length())
        self.op = op # operation
        self.e = e # identity element
        self.v = [None]*(2*self.N-1)
        
        # construction
        for i in range(self.N):
            self.v[i + self.N - 1] = lst[i] if i < self.n else self.e
        for i in range(self.N - 2, -1, -1):
            self.v[i] = self.op(self.v[2*i + 1], self.v[2*i + 2])
        
    # update a_i to be x 
    def update(self, i, x):
        i += self.N - 1
        self.v[i] += x
        while i > 0:
            i -= 1
            i >>= 1
            self.v[i] = self.op(self.v[2*i + 1], self.v[2*i+2])
    
    # returns answer for the query interval [l, r)
    def query(self, l, r):
        assert l < r
        left = l + self.N - 1
        right = r + self.N - 1
        L = self.e
        R = self.e
        while left < right:
            if left % 2 == 0: # left is even
                L = self.op(L, self.v[left])
                left += 1
            if right % 2 == 0: # right is even
                right -= 1
                R = self.op(self.v[right], R)
            left -= 1
            left >>= 1
            right >>= 1
        return self.op(L, R)

n, q = map(int, input().split())
A = [0]*n
st = SegmentTree(A, lambda x, y: x+y, 0)
for _ in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        st.update(x-1, y)
    else:
        print(st.query(x-1, y))

Submission status: Accepted

Solution code:

n, q = map(int, input().split())
size = 1
while size < n:
    size *= 2
size = size
seg_tree = [0]*(size*2)

def update(i, x):
    ind = size-1+i
    seg_tree[ind] += x
    while ind>1:
        ind = ind//2
        left = seg_tree[ind*2]
        right = seg_tree[ind*2+1]
        seg_tree[ind] = left + right

def _find(s,t,i,l,r):
    if r < s or t < l:return 0
    if s <= l and r <= t:
        return seg_tree[i]
    else:
        left = _find(s,t,i*2,l, (l+r)//2)
        right = _find(s,t,i*2+1,(l+r)//2+1,r)
        return left+right

def find(s,t):
    return _find(s,t,1,1,size)

for _ in range(q):
    com, x, y = map(int, input().split())
    if not com:
        update(x, y)
    else:
        print(find(x,y))

Submission status: Accepted

Solution code:
class BinaryIndexedTree:
    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 reset(self):
        self.bit = [0] * (self.n + 1)


N, Q = map(int, input().split())
BIT = BinaryIndexedTree(N)
for q in range(Q):
    com, x, y = map(int, input().split())
    if com == 0:
        BIT.add(x, y)
    if com == 1:
        print(BIT.sum(y) - BIT.sum(x - 1))

Submission status: Accepted

Solution code:
'''
セグメント木
配列バージョン
'''

N, Q = map(int, input().split())
pn = 1
while pn < N:
    pn *= 2
N = pn
A = [0]*(2*N-1)


def add(x, y):
    n = N+x-1
    A[n] += y
    while n > 0:
        n = (n-1)//2
        A[n] += y


def getSum(k, x, y, s, t):
    '''
    範囲[x,y)
    区間[s,t)
    '''
    #print("sum ", x, y, s, t)
    # 交差しない
    if x >= t or y <= s:
        #print("no intersect", x, y, s, t)
        return 0
    # 範囲が区間を包含する
    if x <= s and t <= y:
        #print("intersect ", x, y, s, t)
        return A[k]

    # それ以外
    #print("other ", x, y, s, t)
    lv = getSum(2*k+1, x, y, s, (s+t)//2)
    rv = getSum(2*k+2, x, y, (s+t)//2, t)
    return lv+rv


for i in range(Q):
    com, x, y = map(int, input().split())
    if com == 0:
        add(x-1, y)
    else:
        print(getSum(0, x-1, y, 0, N))
    # print(A)

Submission status: Accepted

Solution code:
import math


def update(numlist,i):
  if i<0:
    return
  if i==0:
    numlist[i]=numlist[2*i+1]+numlist[2*i+2]
    return
  numlist[i]=numlist[2*i+1]+numlist[2*i+2]
  update(numlist,(i-1)//2)
  return

def find(numlist,x,y,k,minimum,maximum):
  if x>=maximum or y<minimum:
    return 0
  if x<=minimum and maximum-1<=y:
    return numlist[k]
  else:
    L=find(numlist,x,y,k*2+1,minimum,(maximum+minimum)//2)
    R=find(numlist,x,y,k*2+2,(maximum+minimum)//2,maximum)
    return L+R
    
  

n,q=map(int,input().split())
L2n=math.ceil(math.log2(n))
zero=2**(L2n)-1
MAX=2**31-1
numlist=[0]*(2**(L2n+1)-1)
resultlist=[]

for _ in range(0,q):
  com,x,y=map(int,input().split())
  if com:
    resultlist.append(find(numlist,x-1,y-1,0,0,2**L2n))
  else:
    numlist[zero+x-1]+=y
    update(numlist,(zero+x-2)//2)

for x in resultlist:
  print (x)

Submission status: Accepted

Solution code:
class SegTree:
    '''Segment Tree:
    Data structure to answer queries on segments of a sequence.
    '''
    def __init__(self,n,init_num,func):
        '''Create a segment tree.
        :param n: Size
        :type n: int or float (number)
        :param init_num: Initialization number
        :type init_num: int or float (number)
        :param func: Function to use
        :type func: function
        '''
        self.func=func
        self.init_num=init_num
        self.size = 2**(len(bin(n-1))-2)*2-1
        self.tree = [init_num for i in range(self.size)]
     
    def data(self):
        '''Return data.
        '''
        return self.tree[self.size//2:]
 
    def update(self,i,x,update_func):
        '''Update the i-th data by update_func.
            example:
            a[i]<-update_func(a[i],x)
        '''
        i=self.size//2+i
        self.tree[i]=update_func(self.tree[i],x)
        while 1:
            i=(i-1)//2
            self.tree[i]=self.func(self.tree[i*2+1],self.tree[i*2+2])
            if i<=0:
                break
 
    def _check(self,s,t,l,r,_p=0):
        if s<=l and r<=t:
            return self.tree[_p]
        elif r<s or t<l:
            return self.init_num
        else:
            return self.func(self._check(s,t,l,l+(r-l)//2,_p*2+1),self._check(s,t,l+(r-l)//2+1,r,_p*2+2))
 
    def find(self,s,t):
        '''Answer queries on [s,t]segment
        '''
        return self._check(s,t,0,self.size//2)

n,q=map(int,input().split())
st=SegTree(n,0,lambda x,y:x+y)
for i in range(q):
    c,x,y=map(int,input().split())
    if c:
        print(st.find(x-1,y-1))
    else:
        st.update(x-1,y,lambda x,y:x+y)

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
Q=[list(map(int,input().split())) for i in range(q)]

#Segment tree（区間の和を求めるバージョン）
for i in range(30):#要素数以上の2のベキを見つける
    if n<1<<i:
        seg_el=1<<i#Segment treeの台の要素数
        break

SEG=[0]*(2*seg_el-1)#Segment treeを一次元リストとして作る

def update(n,x,seg_el):#A[n]+=x
    i=n+seg_el-1
    SEG[i]+=x
    i=(i-1)//2
    
    while i>=0:
        SEG[i]+=x
        i=(i-1)//2
        
def getvalues(a,b,k,l,r):#区間[a,b)での,SEG[k],つまり区間[l,r)に関する和を調べる
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば,0を出力
        return 0
    if a<=l and r<=b:#区間[a,b)が対象区間の中にあればSEG[k]を出力
        return SEG[k]
    vl=getvalues(a,b,k*2+1,l,(l+r)//2)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け（木の子ノード二つを見る）
    vr=getvalues(a,b,k*2+2,(l+r)//2,r)
    return vl+vr

for com,x,y in Q:
    if com==0:
        update(x,y,seg_el)
    else:
        print(getvalues(x,y+1,0,0,seg_el))

Submission status: Accepted

Solution code:
class BIT():
    """数列aに対して以下の操作がO(log n) でできる
    - add(i,x): a[i] += x
    - sum_1_to_i(i): 区間[1, i]のaの総和
    
    sum_i_to_j(i,j): 区間[i,j]のaの総和
    数列aは0に初期化されているとする"""
    def __init__(self, n:int):
        self.n = n
        self.bit = [0]*(n+1)
        
    def add(self, i:int, x:int):
        """i番目(1-idexed)にxを加算"""
        while i<=self.n:
            self.bit[i] += x
            i += i&-i
            
    def sum_1_to_i(self, i:int)->int: 
        """1番目からi番目(含む)までの総和"""
        s=0
        while i>0:
            s += self.bit[i]
            i -= i&-i
        return s
    
    def sum_i_to_j(self, i:int, j:int):
        """i番目からj番目(含む)までの総和"""
        return self.sum_1_to_i(j) - self.sum_1_to_i(i-1)
    
#####
n,q = map(int, input().split())
bit = BIT(n)
for _ in range(q):
    com,x,y = map(int, input().split())
    if com==0:
        bit.add(x,y)
    else:
        print(bit.sum_i_to_j(x,y))