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:
class RSQ:
    def __init__(self, length, ini_num = float("inf")):
        self.length = 1
        self.ini_num = ini_num
        if length == 1:
            length = 2
        while self.length < length:
            self.length <<= 1
        self.segtree = [ini_num] * (2 * self.length - 1)

    def update(self, index, num):
        leaf_index = index + self.length - 1
        self.segtree[leaf_index] = num
        while leaf_index > 0:
            leaf_index = (leaf_index - 1) // 2
            self.segtree[leaf_index] = self.segtree[2 * leaf_index + 1] + self.segtree[2 * leaf_index + 2]

    def add(self, index, num):
        leaf_index = index + self.length - 1
        self.segtree[leaf_index] += num
        while leaf_index > 0:
            leaf_index = (leaf_index - 1) // 2
            self.segtree[leaf_index] = self.segtree[2 * leaf_index + 1] + self.segtree[2 * leaf_index + 2]

    def call_search(self, a, b):
        return self.search(a, b, index = 0, l = 0, r = self.length - 1)

    def search(self, a, b, index, l, r):
        if a <= l <= r <= b:
            return self.segtree[index]
        elif r < a or b < l:
            return self.ini_num
        else:
            return self.search(a, b, index * 2 + 1, l, (l + r) // 2) + self.search(a, b, index * 2 + 2, (l + r) // 2 + 1, r)

v_num, query = map(int, input().split(" "))
rsq = RSQ(v_num, 0)
for _ in range(query):
    comm, index, num = map(int, input().split(" "))
    if comm == 0:
        rsq.add(index - 1, num)
    else:
        print(rsq.call_search(index - 1, num - 1))

Submission status: Accepted

Solution code:
class RSQ:
    def __init__(self, length, ini_num = float("inf")):
        self.length = 1
        self.ini_num = ini_num
        if length == 1:
            length = 2
        while self.length < length:
            self.length <<= 1
        self.segtree = [ini_num] * (2 * self.length - 1)

    def update(self, index, num):
        leaf_index = index + self.length - 1
        self.segtree[leaf_index] = num
        while leaf_index > 0:
            leaf_index = (leaf_index - 1) // 2
            self.segtree[leaf_index] = self.segtree[2 * leaf_index + 1] + self.segtree[2 * leaf_index + 2]

    def add(self, index, num):
        leaf_index = index + self.length - 1
        self.segtree[leaf_index] += num
        while leaf_index > 0:
            leaf_index = (leaf_index - 1) // 2
            self.segtree[leaf_index] = self.segtree[2 * leaf_index + 1] + self.segtree[2 * leaf_index + 2]

    def call_search(self, a, b):
        return self.search(a, b, index = 0, l = 0, r = self.length - 1)

    def search(self, a, b, index, l, r):
        if r < a or b < l:
            return self.ini_num            
        elif a <= l <= r <= b:
            return self.segtree[index]
        else:
            return self.search(a, b, index * 2 + 1, l, (l + r) // 2) + self.search(a, b, index * 2 + 2, (l + r) // 2 + 1, r)

v_num, query = map(int, input().split(" "))
rsq = RSQ(v_num, 0)
for _ in range(query):
    comm, index, num = map(int, input().split(" "))
    if comm == 0:
        rsq.add(index - 1, num)
    else:
        print(rsq.call_search(index - 1, num - 1))

Submission status: Accepted

Solution code:
class SegmentTree():
	def __init__(self,n):
		self.dat = [0 for _ in range(n*2-1)]
		#index n???????????????????????¢?????????:
		#???????????? : (n-1)//2
		#???????????? : (2n+1) , (2n+2)
		self.n = n

	def update (self,node_index,value):
		""" index?????????value????????´?????? """
		index = node_index + (self.n-1) #node_index????????????dot???index?????????
		self.dat[index] += value

		#?????°????????????????????????????????´????????????
		while index > 0 :
			index = (index - 1) // 2				 #???????????????????????£???
			self.dat[index] = self.dat[index*2+1] + self.dat[index*2+2] #??????????????????????????????

	def querry (self,left,right,nowNode,nowLeft,nowRight):
		"""[left,right):??¢?´¢??????,noeNode:?????¨????????????,[nowLeft,nowRight):?????¨?????????????????????"""

		# ??????????????¶??£????????????
		if nowRight < left or nowLeft > right:
			return 0

		# ?????¨?????¢?´¢???????????¨????????????????????????????????????
		if left <= nowLeft and nowRight <= right:
			return self.dat[nowNode]

		# ???????????????????????????????????¨???????????????
		else:
			value_left = self.querry(left,right,2*nowNode+1,nowLeft,(nowLeft+nowRight)//2)
			value_right = self.querry(left,right,2*nowNode+2,(nowLeft+nowRight)//2+1,nowRight)
			return (value_left + value_right)

	def DEBUG_dat(self):
		print(self.dat)


if __name__ == "__main__":
	n ,q  = map(int,input().split(" "))
	result = []

	for i in range(1,20):
		if 2 ** i >= n:
			min_pow2 = 2 **  i
			break

	tree = SegmentTree(min_pow2)

	for i in range(q):
		com,x,y = map(int,input().split(" "))
		if com == 0:
			tree.update(x-1,y)
		else:
			result.append(tree.querry(x-1,y-1,0,0,min_pow2-1))

	for ans in result:
		print(ans)

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, n):
        self.n = n
        self.array = [0 for i in range(n + 1)]

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

    def range_sum(self, i, j):
        tmp_i = self.sum(i - 1)
        tmp_j = self.sum(j)
        return tmp_j - tmp_i

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


init = [int(n) for n in input().split()]
a = []

bit = BIT(init[0])

for i in range(init[1]):
    line = [int(n) for n in input().split()]
    if line[0] == 0:
        bit.add(line[1], line[2])
    else:
        print(bit.range_sum(line[1], line[2]))

Submission status: Accepted

Solution code:
import sys;

def init(n_):
    length = 1;
    while(length < n_):
        length*=2
    element = [0]*(2*length-1)
    for i in range(2*length-1):
        element[i] = 0
    return element,length

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

def findmin(a, b):
    return findquery(a,b+1,0,0,n)

def findquery(a, b, k, l, r):
    if(r <= a or b <= l):
        return 0
    if(a <= l and r <= b):
        return element[k]

    vl = findquery(a,b,k*2+1,l,(int)((l+r)/2+0.5))
    vr = findquery(a,b,k*2+2,(int)((l+r)/2),r)
    return vl+vr

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

element,n = init(n)

for i in range(q):
    query,key,value = map(int, input().split());
    if(query == 0):
        update(key-1,value,element)
    else :
        print(findmin(key-1,value-1))

Submission status: Accepted

Solution code:

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

n_ = 1 # 実際に確保した配列のサイズ
while n_ < n:
  n_ *= 2

seg_tree = [0 for i in range(2*n_-1)]

def add(i, x):
  i += n_ - 1
  seg_tree[i] += x
  while i > 0 :
    i = int((i - 1)/2)
    #seg_tree[i] = seg_tree[i*2+1] + seg_tree[i*2+2]
    seg_tree[i] += x

def getSum(s, t):
  return query(s, t+1, 0, 0, n_)

def query(a, b, k, l, r):
  if r <= a or b <= l :
    return 0
  if a <= l and r <= b:
    return seg_tree[k]

  vl = query(a, b, k*2+1, l, int((l+r)/2))
  vr = query(a, b, k*2+2, int((l+r)/2), r)
  return vl + vr


output = []

for i in range(q):
  # print(seg_tree)
  line = list(map(int, input().split()))

  if line[0] == 0:
    add(line[1]-1, line[2])

  else :
    output.append(getSum(line[1]-1,line[2]-1))


for ans in output:
  print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)


def initRMQ(n):
    n_ = 1

    while n_ < n:
        n_ *= 2

    D = []
    for _ in range(2*n_ - 1):
        D.append(0)

    return n_, D


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


def findSum(a, b):
    return query(a, b + 1, 0, 0, n_)


def query(a, b, k, l, r):
    #print('q', a, b, k, l, r)
    if r <= a or b <= l:
        return 0

    if a <= l and r <= b:
        return D[k]

    vl = query(a, b, k*2 + 1, l, int((l + r)/2))
    vr = query(a, b, k*2 + 2, int((l + r)/2), r)

    return vl + vr


if __name__ == '__main__':
    n, q = map(int, input().split())

    n_, D = initRMQ(n)

    for _ in range(q):
        #print(D)
        c, x, y = map(int, input().split())

        if c == 0:
            update(x - 1, y)

        else :
            print(findSum(x - 1, y - 1))

Submission status: Accepted

Solution code:
# Range Sum Query (RSQ)
D = [0]
[n, q] = list(map(int, input().split()))

def initRMQ(n_):
    global D, n
    size = 1
    while size < n_:
        size *= 2
    i = 1
    while i <= 2*size - 1 - 1:
        D.append(0)
        i += 1
    n = size

def add(k, a):
    global D
    k += n - 1
    D[k] += a
    while k > 0:
        k = int((k - 1)/2)
        D[k] = D[k*2 + 1] + D[k*2 + 2]

def query(a, b, k, l, r):
    global D
    if r <= a or b <= l:
        return 0
    if a <= l and r <= b:
        return D[k]

    vl = query(a, b, k*2 + 1, l, int((l + r)/2))
    vr = query(a, b, k*2 + 2, int((l + r)/2), r)
    return vl + vr

def getSum(a, b):
    global n
    return query(a, b + 1, 0, 0, n)

initRMQ(n)
for i in range(q):
    data = list(map(int, input().split()))
    if data[0] == 0:
        add(data[1] - 1, data[2])
    if data[0] == 1:
        print(getSum(data[1] - 1, data[2] - 1))

Submission status: Accepted

Solution code:
import math

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

    def add(self, idx, val):
        while idx <= self.N:
            self.tree[idx] += val
            idx += (idx & -idx)

    def sum_to(self, idx):
        result = 0
        while idx > 0:
            result += self.tree[idx]
            idx -= (idx & -idx)
        return result

n, q = map(int, input().split())
bit = BinaryIndexedTree(n)
for _ in range(q):
    com, n1, n2 = map(int, input().split())
    if com == 0:
        bit.add(n1, n2)
    else:
        print(bit.sum_to(n2) - bit.sum_to(n1-1))

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, N_, element, function_=(lambda l, r: l + r)):
        """
        :param N_: セグ木のサイズ
        :param element: 単位元
        :param function: 子の要素に対して行われる計算,デフォルトだと加算
        """
        self.N = 1
        while self.N < N_:
            self.N *= 2

        self.element = element
        self.dat = [element for _ in range(self.N * 2)]
        self.function = function_

    def update(self, k, a):
        """k番目の値(0-indexed)をaに変更"""
        k += self.N - 1
        self.dat[k] = a

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

    def query(self, begin, end, k=None, l=None, r=None):
        if k is None: return self.query(begin, end, 0, 0, self.N)

        if r <= begin or end <= l: return self.element
        if begin <= l and r <= end: return self.dat[k]

        vl = self.query(begin, end, k * 2 + 1, l, (l + r) // 2)
        vr = self.query(begin, end, k * 2 + 2, (l + r) // 2, r)
        return self.function(vl, vr)


n, q = map(int, input().split())
n += 1
treeone = SegmentTree(n, 0, (lambda l, r: l + r))

while q > 0:
    q -= 1
    tmp = list(map(int, input().split()))
    if tmp[0] is 0:
        treeone.update(tmp[1],treeone.query(tmp[1], tmp[1] + 1) + tmp[2])
    else:
        print(treeone.query(tmp[1], tmp[2] + 1))

Submission status: Accepted

Solution code:
import math

class SegmentTree():
    def __init__(self, n):
        self.n = n
        self.height = math.ceil(math.log2(n))
        self.nodes = [0 for i in range(pow(2, self.height+1)-1)]
        self.leaf_start = pow(2, self.height)-1

    def update(self, i, x):
        pntr = self.leaf_start + i
        self.nodes[pntr] += x
        while True:
            pntr = (pntr-1)//2
            if pntr == -1: break
            self.nodes[pntr] += x

    def __query(self, s, t, k, l, r):
        if t - s <= 0: return 0
        if r <= s or t <= l: return 0
        if l == s and t == r: return self.nodes[k]
        else:
            m = (l+r)//2
            if t <= m:
                return self.__query(s, t, k*2+1, l, m)
            elif m <= s:
                return self.__query(s, t, k*2+2, m, r)
            else:
                vl = self.__query(s, m, k*2+1, l, m)
                vr = self.__query(m, t, k*2+2, m, r)
                return vl + vr

    def find(self, s, t):
        return self.__query(s, t+1, 0, 0, pow(2, self.height))

n, q = list(map(int, input().split(' ')))
st = SegmentTree(n)
for i in range(q):
    com, x, y = list(map(int, input().split(' ')))
    if com == 0:
        st.update(x-1, y)
    elif com == 1:
        print(st.find(x-1, y-1))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


def main(readline=stdin.readline):
    n, q = (int(s) for s in readline().split())

    a = [0] * n
    b = [0] * (n // 100 + 1)

    for _ in range(q):
        com, x, y = (int(s) for s in readline().split())
        if com:
            x -= 1
            bx = x - x % 100 + 100
            by = y - y % 100
            if bx < by:
                s = sum(a[x:bx]) + sum(b[bx//100:by//100]) + sum(a[by:y])
            else:
                s = sum(a[x:y])
            print(s)
        else:
            x -= 1
            a[x] += y
            bx = x - x % 100
            b[x//100] = sum(a[bx:bx+100])


main()

Submission status: Accepted

Solution code:
class SEGTree:
    def __init__(self,n,fanction,unit):
        self.Unit=unit
        i=1<<(n.bit_length()-1)
        if i!=n:
            i*=2
        self.Fanction=fanction
        self.SEG=[self.Unit]*(2*i-1)
        self.d=i
    def update(self,i,x):
        i+=self.d-1
        self.SEG[i]+=x
        while i>0:
            i=(i-1)//2
            self.SEG[i]=self.Fanction(self.SEG[i*2+1],self.SEG[i*2+2])
    def find(self,a,b,k,l,r):
        if r<=a or b<=l:
            return self.Unit
        if a<=l and r<=b:
            return self.SEG[k]
        else:
            c1=self.find(a,b,2*k+1,l,(l+r)//2)
            c2=self.find(a,b,2*k+2,(l+r)//2,r)
            return self.Fanction(c1,c2)
    def get(self,a,b):
        return self.find(a,b,0,0,self.d)

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

n,q=map(int,input().split())
SEG=SEGTree(n,sumint,0)
for _ in range(q):
    com,x,y=map(int,input().split())
    x-=1
    if com==0:
        SEG.update(x,y)
    else:
        print(SEG.get(x,y))

Submission status: Accepted

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

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)

bit=BIT(n+1)

for i in range(q):
   com,x,y=map(int,input().split())
   if com==0:
      bit.add(x,y)
   else:
      s = bit.get(x-1,y)
      print(s)

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, size, f=lambda x, y: x + y, default=0):
        self.size = 2 ** (size - 1).bit_length()
        self.default = default
        self.dat = [default] * (self.size * 2)
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i * 2], self.dat[i * 2 + 1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres)
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res


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

Submission status: Accepted

Solution code:
class SegTree:
    """
    内部実装1-indexed．
    set_valやfoldには0-indexedでアクセス．
    2べきに直さなくてよい．
    Range Sum Query．
    X_unit 0 X_f sum
    """
    from operator import add
    X_unit = 0
    X_f = add

    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] += x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)


def main():
    N, Q = (int(i) for i in input().split())
    seg = SegTree(N)
    for _ in range(Q):
        com, x, y = (int(i) for i in input().split())
        if com == 0:
            seg.set_val(x-1, y)
        else:
            print(seg.fold(x-1, y))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

BIT = []
n = 0


def init():
    # 初期化
    global BIT, n

    BIT = [0] * (n + 1)  # BIT は 最初のインデックスは 1(0001)


def add(i, x):

    global BIT, n

    # A[i] に x を加える動作
    while i < n + 1:
        BIT[i] += x
        i += (i & -i)  # i & -i は最下位ビットを取り出す動作


def sum(i):
    # i までの和

    global BIT, n

    _sum = 0
    while i > 0:
        _sum += BIT[i]
        i -= (i & -i)  # i & -i は最下位1ビットを表す

    return _sum


def main():

    global BIT, n
    n, q = map(int, sys.stdin.readline().rstrip().split())

    init()

    # print(n, len(BIT), BIT)

    for _ in range(q):
        com, x, y = map(int, sys.stdin.readline().rstrip().split())

        if com == 0:
            add(x, y)
            # print("add", BIT)
        else:
            # print(BIT)
            print(sum(y) - sum(x - 1))


main()

Submission status: Accepted

Solution code:
# Binary Indexed Tree (Fenwick Tree)
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 solve():
  N, Q = map(int, input().split())
  ans = []
  bit = BIT(N)
  for i in range(Q):
    com,x,y = map(int, input().split())
    if com==0:
      bit.add(x,y)
    else:
      ans.append(bit.get(x-1,y))
  return ans
print(*solve(),sep='\n')

Submission status: Accepted

Solution code:
# Binary indexed tree
class BIT():
    def __init__(self,n):
        self.array = [0] * n
        self.N = n

    # 1番目からi番目までの累積和を求める
    def sum(self,i):
        s = 0
        while i > 0:
            s += self.array[i-1]
            i -= i&(-i)
        return s

    # sum(i,j)
    def sum2(self,i,j):
        return self.sum(j) - self.sum(i-1)

    # i番目にxを追加
    def add(self,i,x):
        while i <= self.N:
            self.array[i-1] += x
            i += i&(-i)

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

for i in range(Q):
    com, x, y = map(int, input().split())
    if com:
        res = bit.sum2(x,y)
        print(res)
    else:
        bit.add(x,y)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    n,q = LI()
    bit = [0] * (n+1)

    def bit_add(i,x):
        while i <= n:
            bit[i] += x
            i += i & (-i)

    def sum_bit(i):
        ret = 0
        while i > 0:
            ret += bit[i]
            i -= i & (-i)
        return ret

    for _ in range(q):
        c,x,y = LI()
        if c == 0:
            bit_add(x,y)
        else:
            ans = sum_bit(y) - sum_bit(x-1)
            print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def _max(a,b):
    return max(a,b)

def _min(a,b):
    return min(a,b)

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

class SegmentTree:

    def __init__(self, a):
        sz = len(a)
        self.n = int(1)
        while self.n < sz:
            self.n = int(self.n*2)

        self.func = _sum
        self.init = 0

        self.val = [0]*(self.n*2 - 1)
        self.val[self.n-1:self.n-1+sz] = a
        for i in range(self.n-2, -1, -1):
            self.val[i] = self.func(self.val[2*i+1], self.val[2*i+2])

    def update(self, pos, x):
        # 0-indexed
        k = int(pos + self.n-1)
        self.val[k] += x
        while k > 0:
            k = int(k-1) // 2
            self.val[k] = self.func(self.val[2*k+1], self.val[2*k+2])

    def query(self, a, b, k=0, l=0, r=-1):
            # 0-indexed
            # [a,b)に対してquery
            if r < 0:
                r = self.n
            if r <= a or b <= l:
                return self.init
            if a <= l and r <= b:
                return self.val[k]

            lv = self.query(a, b, 2*k+1, l, (l+r)//2)
            rv = self.query(a, b, 2*k+2, (l+r)//2, r)
            return self.func(lv, rv)

    def get(self, pos):
        # 0-indexed
        return self.val[pos + self.n-1]

n,q = map(int, input().split())
a = [0]*n
st = SegmentTree(a)

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

    x -= 1
    if t == 0:
        st.update(x,y)
    else:
        ans = st.query(x,y)
        print(int(ans))

Submission status: Accepted

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

#from collections import defaultdict
#from heapq import heappush, heappop
#import numpy as np
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 2 ** 31 - 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7

debug_indent = 0


def debug(*x):
    global debug_indent
    x = list(x)
    indent = 0
    if x[0].startswith("enter") or x[0][0] == ">":
        indent = 1
    if x[0].startswith("leave") or x[0][0] == "<":
        debug_indent -= 1
    x[0] = "  " * debug_indent + x[0]
    print(*x, file=sys.stderr)
    debug_indent += indent


def set_depth(depth):
    global N, SEGTREE_SIZE, NONLEAF_SIZE
    N = depth
    SEGTREE_SIZE = 1 << N
    NONLEAF_SIZE = 1 << (N - 1)


def point_set(table, pos, value, binop):
    pos = pos + NONLEAF_SIZE
    table[pos] = value
    while pos > 1:
        pos >>= 1
        table[pos] = binop(
            table[pos * 2],
            table[pos * 2 + 1],
        )


def point_update(table, pos, action):
    pos = pos + NONLEAF_SIZE
    table[pos] = action(table[pos])
    while pos > 1:
        pos >>= 1
        table[pos] = action(table[pos])


def range_reduce(table, left, right, binop, unity):
    ret_left = unity
    ret_right = unity
    left += SEGTREE_SIZE // 2
    right += SEGTREE_SIZE // 2
    while left < right:
        if left & 1:
            ret_left = binop(ret_left, table[left])
            left += 1
        if right & 1:
            right -= 1
            ret_right = binop(table[right], ret_right)

        left //= 2
        right //= 2
    return binop(ret_left, ret_right)


def main():
    from operator import add
    N, Q = map(int, input().split())
    depth = N.bit_length() + 1
    set_depth(depth)
    table = [0] * SEGTREE_SIZE

    for _q in range(Q):
        q, x, y = map(int, input().split())
        if q == 0:
            # add
            point_update(table, x, lambda x: x + y)
        else:
            # find
            print(range_reduce(table, x, y + 1, add, 0))


# tests
T1 = """
3 5
0 1 1
0 2 2
0 3 3
1 1 2
1 2 2
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    3
    2
    """
# add tests above


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Accepted

Solution code:
class SegT():
    # originは初期データがあれば渡す
    def __init__(self, size, origin=None):
        self.size = 1
        while self.size < size: self.size *= 2
        self._data_init()
        if origin:
            for i in range(size):
                self.data[i+self.size-1] = origin[i]
            for i in range(self.size-2,-1,-1):
                self.data[i] = self._calc(self.data[i*2+1], self.data[i*2+2])

    def _data_init(self):
        self.e = 0 # 単位元
        self.data = [self.e for _ in range(self.size * 2 - 1)]

    def _calc(self, a, b):
        # ここは独自実装する
        return a + b

    def update(self, i, x):
        i += (self.size - 1)
        self.data[i] += x # ここも書き直す
        while i > 0:
            i = (i - 1) // 2
            self.data[i] = self._calc(self.data[i*2+1], self.data[i*2+2])
        
    def get(self, a, b, node=0, l=0, r=-1):
        if r < 0: r = self.size
        if r <= a or b <= l: return self.e
        if a <= l and r <= b: return self.data[node]
        vl = self.get(a, b, node*2+1, l, (l+r)//2)
        vr = self.get(a, b, node*2+2, (l+r)//2, r)
        return self._calc(vl, vr)

N, Q = map(int, input().split())
origin = [pow(2, 31) - 1 for i in range(N)]
segt = SegT(N)

for i in range(Q):
    t, l, r = input().split()
    if t == "0":
        segt.update(int(l)-1, int(r))
    else:
        x = segt.get(int(l)-1,int(r))
        print(x)

Submission status: Accepted

Solution code:
from operator import add
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


class SegmentTree:
    def __init__(self, N, arr=None, op=None, unit=None):
        self.N = N
        self.unit = unit
        self.op = op
        self.tree = [unit] * (2 * N + 1)
        if arr is not None:
            self._build(arr)

    def _build(self, arr):
        op = self.op
        N = self.N
        for i, a in enumerate(arr, N):
            self.tree[i] = a
        for i in reversed(range(1, N)):
            self.tree[i] = op(self.tree[i << 1], self.tree[i << 1 | 1])

    def update(self, i, x):
        """
        arr[i]の値をxに変更する
        i: 0-indexed
        """
        i += self.N
        op = self.op
        self.tree[i] += x
        while i > 1:
            i >>= 1
            self.tree[i] = op(self.tree[i << 1], self.tree[i << 1 | 1])

    def query(self, L, R):
        """
        L,R: 0-indexed
        半開区間[L,R)の累積演算した値を返す
        """
        op = self.op
        res = self.unit
        L += self.N
        R += self.N
        while L < R:
            if L & 1:
                res = op(res, self.tree[L])
                L += 1
            if R & 1:
                R -= 1
                res = op(res, self.tree[R])
            L >>= 1
            R >>= 1
        return res


if __name__ == "__main__":
    N, Q = map(int, input().split())
    query = tuple(tuple(map(int, input().split())) for _ in range(Q))
    seg = SegmentTree(N, [0]*N, add, 0)

    ans = []
    for f, x, y in query:
        if f:
            ans.append(seg.query(x-1, y))
        else:
            seg.update(x-1, y)
    print(*ans, sep="\n")

Submission status: Accepted

Solution code:
from math import sqrt, floor

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

A = [0] * (n + 1)

# sqrt-decomposition
b = floor(sqrt(n + 1))
k = (n + b) // b
# Aをbごとに分割して、総和をBで管理する
# B[i] represents sum of A[i*b: (i+1)*b]
B = [0] * k


def add(x, y):
    A[x] += y
    B[x//b] += y


def get_sum(x, y):
    res = 0
    # xから bの倍数になるまで足す
    while x % b and x < y:
        res += A[x]
        x += 1
    # yから bの倍数になるまで、添字が減る方向に足す
    while y % b and x < y:
        res += A[y]
        y -= 1
    res += A[y]
    # 残りの間の区間を足す
    res += sum(B[x//b:y//b])

    print(res)


for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        add(x, y)
    else:
        get_sum(x, y)