Problem:
Range Sum Query Write a program which manipulates a sequence A = { a 1 , a 2 , . . . , a n } with the following operations:  add(i, x) : add x to a i .  getSum(s, t) : print the sum of a s , a s+1 ,...,a t .  Note that the initial values of a i ( i = 1, 2, . . . , n ) are 0. Input  n  q  com 1  x 1  y 1  com 2  x 2  y 2 ... com q  x q  y q  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(x i , y i ) and '1' denotes getSum(x i , y i ) . Output For each getSum operation, print the sum in a line. Constraints   1 ≤ n ≤ 100000    1 ≤ q ≤ 100000   If com i is 0, then 1 ≤ x i ≤ n , 0 ≤ y i ≤ 1000 .  If com i is 1, then 1 ≤ x i ≤ n , 1 ≤ y i ≤ 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

Solution (Python):

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] += 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):
  
  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)

Solution (Python):
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):
    
    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):
        
        c, x, y = map(int, input().split())

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

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

Solution (Python):

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

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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))

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

Solution (Python):
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))

Solution (Python):
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):
        
        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)

Solution (Python):
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))

Solution (Python):
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()

Solution (Python):
import sys

BIT = []
n = 0


def init():
    
    global BIT, n

    BIT = [0] * (n + 1)  


def add(i, x):

    global BIT, n

    
    while i < n + 1:
        BIT[i] += x
        i += (i & -i)  


def sum(i):
    

    global BIT, n

    _sum = 0
    while i > 0:
        _sum += BIT[i]
        i -= (i & -i)  

    return _sum


def main():

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

    init()

    

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

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


main()

Solution (Python):

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

Solution (Python):

class BIT():
    def __init__(self,n):
        self.array = [0] * n
        self.N = n

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

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

    
    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)

Solution (Python):
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()

Solution (Python):
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):
        
        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):
            
            
            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):
        
        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))

Solution (Python):





import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 2 ** 31 - 1  
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:
            
            point_update(table, x, lambda x: x + y)
        else:
            
            print(range_reduce(table, x, y + 1, add, 0))



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



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":
        
        
        from my_module import solve  
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Solution (Python):
class SegT():
    
    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)

Solution (Python):
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")

Solution (Python):
from math import sqrt, floor

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

A = [0] * (n + 1)


b = floor(sqrt(n + 1))
k = (n + b) // b


B = [0] * k


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


def get_sum(x, y):
    res = 0
    
    while x % b and x < y:
        res += A[x]
        x += 1
    
    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)

Solution (Python):
import time

class segTree:
    size = 0
    data = []
    __unitElement = 0
    __tree = []
    __totalSize = 0
    
    def __init__(self, inputData):
        self.data = inputData
        tmp = 1
        while tmp < len(inputData):
            tmp *= 2
        self.size = tmp
        self.__totalSize = 2*self.size-1
        self.__tree = [self.__unitElement]*self.__totalSize
        for i in range(len(inputData)):
            self.change(i, inputData[i])
    
    def change(self, i, x):
        self.data[i] = x
        cur = self.size-1+i
        self.__tree[cur] = x
        while True:
            cur = cur-1
            if cur < 0:
                break
            cur = cur//2
            
            self.__tree[cur] = self.__tree[2*cur+1] + self.__tree[2*cur+2]
  

    def __queryBody(self, i, a, b, left, right):
        if right <= a or b <= left: 
            return self.__unitElement
        elif a <= left and right <= b:
            return self.__tree[i]
        else:
            mid = (left+right)//2
            child1 = self.__queryBody(2*i+1, a, b, left, mid)
            child2 = self.__queryBody(2*i+2, a, b, mid, right)
            return child1 + child2 
            
    
    def query(self, a, b):
        return self.__queryBody(0, a, b, 0, self.size)
        



n, q = map(int, input().split())
s = segTree([0]*n)  

for _ in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        cur = s.data[x-1]
        s.change(x-1, cur+y)
    else:
        print(s.query(x-1, y))

Solution (Python):









import sys,collections,math
sys.setrecursionlimit(1000000)

INF = 2**31-1

N,Q = map(int,sys.stdin.readline().split())
COM = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(Q)) 
i = 1
while i < N:
    i*=2
N = i
MAX_N = 1 << math.ceil(math.log2(N)) 
SEG = [0]*(2*MAX_N-1)

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

def find(a,b,i=0,l=0,r=N):
    
    if r <= a or  b <= l:
        return 0
    if a <= l and r <= b:
        return SEG[i]
    vl = find(a,b,2*i+1,l,(r+l)//2)
    vr = find(a,b,2*i+2,(r+l)//2,r)
    return vl+vr


for com,x,y in COM:
    if com == 0:
        update(x-1,y)
        
    else:
        print(find(x-1,y))

Solution (Python):
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def sum_range(self, x, y):
        return self.sum(y) - self.sum(x - 1)
  
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


if __name__ == '__main__':
    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_range(x, y))

Solution (Python):
def main():
	import sys
	input=sys.stdin.readline
	n,q=map(int,input().split())
	seg=[]
	cnt=-1
	inf=2**31-1
	while 2**cnt<=n:
		cnt+=1
		seg.append([0 for _ in range(2**cnt)])
	
	def f(i,j):
		Range=(2**(cnt-i)*j,2**(cnt-i)*(j+1)-1)
		if Range[0]>y or Range[1]<x:
			return 0
		elif Range[0]>=x and Range[1]<=y:
			return seg[i][j]
		else:
			return f(i+1,2*j)+f(i+1,2*j+1)
	for _ in range(q):
		c,x,y=map(int,input().split())
		if c==0:
			seg[-1][x]+=y
			x//=2
			for j in range(1,cnt+1):
				seg[-j-1][x]=seg[-j][x*2]+seg[-j][x*2+1]
				x//=2
		else:
			print(f(0,0))
if __name__ == '__main__':
	main()

Solution (Python):
N,Q = map(int,input().split())
bit = [0]*(N+1)
'''
def add(a,w):
    ret = 0
    for i in range(a,0,-(i&-i)):ret += bit[i]
    return ret
'''
def add(a,w):
    x = a
    while x<=N:
        bit[x]+=w
        x+=x&-x
def bsum(a):
    ret = 0
    x = a
    while x>0:
        ret+=bit[x]
        x-=x&-x
    return ret

for i in range(Q):
    l = list(map(int,input().split()))
    if l[0] == 0:
        add(l[1],l[2])
    else:
        print(bsum(l[2])-bsum(l[1]-1))

Solution (Python):

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



ide_ele = 0


class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(N)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

n, q = [int(x) for x in input().split()]
seg = SegTree([0]*n, segfunc, ide_ele)
for _ in range(q):
    com, x, y = [int(x) for x in input().split()]
    if com:
        print(seg.query(x - 1, y))
    else:
        x -= 1
        y += seg.tree[seg.num + x]
        seg.update(x, y)

Solution (Python):
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-1)
        self.f = f

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

    def query(self, l, r, k=0, L=0, R=None):
        if R is None:
            R = self.size
        if R <= l or r <= L:
            return self.default
        if l <= L and R <= r:
            return self.dat[k]
        else:
            lres = self.query(l, r, k*2+1, L, (L+R) >> 1)
            rres = self.query(l, r, k*2+2, (L+R) >> 1, R)
            return self.f(lres, rres)

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

Solution (Python):
"""
Segment-Tree
    maxval:入力されるデータ以上の値
    offset:根と枝の数(n=1のときは根1つ葉2つの木)
    init_array(array):配列で初期化
    update(k,x):k番目をxに変更
    min_query(p,q):[p,q)の範囲の最小値
"""
class SegmentTree():
    def __init__(self,n):
        self.offset=self.setOffset(n)
        self.segTree=[0]*(2*self.offset+1)

    def init_array(self,array):
        for i in range(len(array)):
            self.segTree[i+self.offset]=array[i]
        for i in range(offset-1,-1,-1):
            self.segTree[i]=self.sumChild(i)

    def setOffset(self,n):
        if n==1:
            return 1
        else:
            return 2**(n-1).bit_length()-1

    def update(self,k,x):
        k+=self.offset
        self.segTree[k]+=x
        while k:
            k=(k-1)//2
            self.segTree[k]+=x

    def sum_query(self,p,q):
        if p>=q:
            return

        p+=self.offset
        q+=self.offset-1
        segsum=0

        while q-p>1:
            
            if not p&1:
                segsum+=self.segTree[p]
            
            if q&1:
                segsum+=self.segTree[q]
                q-=1
            p=p//2
            q=(q-1)//2

        if p==q:
            return segsum+self.segTree[p]
        else:
            return segsum+self.segTree[p]+self.segTree[q]

    def sumChild(self,n):
        return self.segTree[2*n+1]+self.segTree[2*n+2]

    def show(self):
        print(self.segTree)

n,q=map(int,input().split())
ST=SegmentTree(n)
for i in range(q):
    qry=list(map(int,input().split()))
    if qry[0]==0:
        ST.update(qry[1]-1,qry[2])
    else:
        print(ST.sum_query(qry[1]-1,qry[2]))