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

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

Submission status: Wrong Answer

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
            y -= 1
            bx = x - x % 100
            by = y - y % 100
            if bx < by:
                s = sum(a[x:bx]) + sum(b[bx//100:by//100]) + sum(a[by:y+1])
            else:
                s = sum(a[x:y+1])
            print(s)
        else:
            x -= 1
            a[x] += y
            bx = x - x % 100
            b[x//100] = sum(a[bx:bx+100])


main()

Submission status: Wrong Answer

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

Solution code:
from sys import stderr
from functools import reduce
from operator import add
def f(): return [int(i) for i in input().split()]
def debug(*x, sep=" ", end="\n"):
    for item in x:
        stderr.write(repr(item))
        stderr.write(sep)
    stderr.write(end)

n,q = f()
que = [0 for i in range(n)]
for i in range(q):
    q,x,y = f()
    if q == 0:
        que[x-1] += y
    elif q == 1:
        print(sum(que[x-1:y]))

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
a = [0]*n


def add(i, x):
    a[i-1] += x


def getSum(s, t):
    ans = 0
    for i in range(s - 1, t):
        ans += a[i]
    print(ans)


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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
n,q = map(int,raw_input().split())
A = [0]*(n+1)
for i in xrange(q):
    com,xi,yi = map(int,raw_input().split())
    if com: # getSum(xi,yi)
        print sum(A[xi:yi+1])
    else: #  add(xi,yi)
        A[xi] += yi

Submission status: Time Limit Exceeded

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

A = [0 for i in range(n + 1)]

for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        A[x] += y
    else:
        s = sum(A[x:y+1])
        print(s)

Submission status: Accepted

Solution code:

class SegmentTree:
    def __init__(self, n):
        size = 1
        while size < n:
            size *= 2
        self.size = 2*size - 1
        self.data = [0] * self.size

    def add(self, i, v):
        # assert 0 <= i <= self.size//2
        index = self.size // 2 + i
        self.data[index] += v
        while index > 0:
            index = (index-1) // 2
            self.data[index] = self.data[index*2 + 1] + self.data[index*2 + 2]

    def sum(self, lo, hi):
        def _sum(r, i, j):
            if j < lo or i > hi:
                return 0
            elif lo <= i and j <= hi:
                return self.data[r]
            else:
                mid = i + (j - i)//2
                return _sum(r*2 + 1, i, mid) + _sum(r*2 + 2, mid+1, j)

        # assert 0 <= lo <= self.size//2
        # assert 0 <= hi <= self.size//2
        # assert lo <= hi

        return _sum(0, 0, self.size//2)


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

    t = SegmentTree(n)
    for _ in range(q):
        com, x, y = [int(i) for i in input().split()]
        if com == 0:
            t.add(x-1, y)
        else:
            print(t.sum(x-1, y-1))


if __name__ == '__main__':
    run()

Submission status: Accepted

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

answer = []
# create segtree
size = 1

while size < n :
    size *= 2
    
size = size * 2 - 1

segtree = [0 for x in range(size)]

# print(size)

# update query
def update(i, x) :
    ind = size // 2 + i
    segtree[ind] += x
    
    while ind :
        ind = (ind - 1) // 2 # parent
        ch1 = segtree[ind * 2 + 1]
        ch2 = segtree[ind * 2 + 2]
        segtree[ind] = ch1 + ch2
    
def query(s, t, l, r, p) :
    if s > r or t < l :
        return 0
    if s <= l and t >= r :
        return segtree[p]
    else :
        vl = query(s, t, l, (l + r) // 2, p * 2 + 1)
        vr = query(s, t, (l + r) // 2 + 1, r, p * 2 + 2)
        
        return vl + vr
    
for i in range(q) :
    # print("DBG : ", segtree)
    com, x, y = map(int, input().split())
     
    if com == 0 :
        update(x - 1, y)
    else :
        answer.append(query(x - 1, y - 1, 0, size // 2, 0))

for a in answer :
    print(a)

Submission status: Accepted

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

# max_num
DEF = 0

# generate seg tree
seg_size = 2

while seg_size < n :
    seg_size *= 2
    
seg_size = seg_size * 2 - 1
seg_tree = [DEF for x in range(seg_size)]

answer_stk = []

# update 
def update(i, x) :
    # leaf for index @ i
    idx = seg_size // 2 + i
    seg_tree[idx] += x
    
    while idx :
        idx = (idx - 1) // 2
        l_child = seg_tree[idx * 2 + 1]
        r_child = seg_tree[idx * 2 + 2]
        
        seg_tree[idx] = l_child + r_child

# query
def query(s, t, l, r, curnode) :
    # no overlap then return INF
    if s > r or t < l :
        return DEF
    
    # full overlap then return current node
    if s <= l and t >= r :
        return seg_tree[curnode]
    
    # partial overlap then return min for next
    else :
        l_child = curnode * 2 + 1
        r_child = curnode * 2 + 2
        
        l_value = query(s, t, l, (l + r) // 2, l_child)
        r_value = query(s, t, (l + r) // 2 + 1, r, r_child)
        
        return l_value + r_value
    
# do main query
for i in range(q) :
    q, x, y = map(int, input().split())
    
    # update
    if q == 0 :
        update(x - 1, y)
        
    # query 
    else :
        answer_stk.append(query(x - 1, y - 1, 0, seg_size // 2, 0))
        
for a in answer_stk :
    print(a)

Submission status: Accepted

Solution code:
import sys


class BIT:
    def __init__(self, node_size):
        self._node = node_size+1
        self.bit = [0]*self._node

    def add(self, index, add_val):
        index += 1
        while index < self._node:
            self.bit[index] += add_val
            index += index & -index

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

if __name__ == '__main__':
    n, q = map(int, sys.stdin.readline().split())
    bt = BIT(n)
    for i in range(q):
        a, b, c = map(int, sys.stdin.readline().split())
        if a == 0:
            bt.add(b-1, c)
        else:
            print(bt.sum(c-1)-bt.sum(b-2))

Submission status: Accepted

Solution code:
import sys


class BIT:
    def __init__(self, node_size):
        self._node = node_size+1
        self.bit = [0]*self._node

    def add(self, index, add_val):
        while index < self._node:
            self.bit[index] += add_val
            index += index & -index

    def sum(self, index):
        res = 0
        while index > 0:
            res += self.bit[index]
            index -= index & -index
        return res

if __name__ == '__main__':
    n, q = map(int, sys.stdin.readline().split())
    bt = BIT(n)
    for i in range(q):
        a, b, c = map(int, sys.stdin.readline().split())
        if a == 0:
            bt.add(b, c)
        else:
            print(bt.sum(c)-bt.sum(b-1))

Submission status: Accepted

Solution code:
dat = [0] * 400000
m = 0

def init():
    global dat, m
    for i in range(2 * m - 1):
        dat[i] = 0

def add(i, x):
    global dat, m
    i += m - 1
    dat[i] += x
    while i > 0:
        i = (i - 1) // 2
        dat[i] = dat[2 * i + 1] + dat[2 * i + 2]

def getSum(a, b, k, l, r):
    global dat, m
    if r <= a or b <= l:
        return 0
    if a <= l and r <= b:
        return dat[k]
    else:
        vl = getSum(a, b, 2 * k + 1, l, (l + r) // 2)
        vr = getSum(a, b, 2 * k + 2, (l + r) // 2, r)
        return vl + vr

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

for _ in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        add(x - 1, y)
    else:
        print(getSum(x - 1, y, 0, 0, m))

Submission status: Accepted

Solution code:
import sys


class BinaryIndexedTree(object):
    __slots__ = ["tree"]

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

    def add(self, index: int, value: int) -> None:
        tree = self.tree
        next_index = index + 1

        while next_index < len(tree):
            tree[next_index] += value
            next_index += next_index & -next_index

    def sum(self, index: int):
        tree, result = self.tree, 0
        next_index = index + 1

        while next_index:
            result += tree[next_index]
            next_index -= next_index & -next_index

        return result


if __name__ == "__main__":
    n, q = map(int, input().split())
    bit = BinaryIndexedTree(n)
    result = []
    for com, x, y in (map(int, l.split()) for l in sys.stdin):
        if not com:
            bit.add(x-1, y)
        else:
            result.append(bit.sum(y-1) - bit.sum(x-2))

    print(*result, sep="\n")

Submission status: Accepted

Solution code:
class TemplateTree:
  def __init__(self, iterable):
    self.iter_size = self.get_size(iterable)
    self.size = self.iter_size * 2 - 1
    self.value = [None] * self.size
    for i, v in enumerate(iterable):
      self.value[self.iter_size + i - 1] = v
    self.set_value(0)
    self.range = [None] * self.size
    self.set_range(0, 0, self.iter_size - 1)
  
  def get_size(self, iterable):
    ret = 1
    x = len(iterable)
    while ret < x:
      ret *= 2
    return ret
  
  def set_range(self, x, left, right):
    self.range[x] = (left, right)
    if left != right:
      self.set_range(x * 2 + 1, left, (right + left) // 2)
      self.set_range(x * 2 + 2, (right + left) // 2 + 1, right)

  def set_value(self, x):
    if x >= self.iter_size - 1:return self.value[x]
    a = self.set_value(x * 2 + 1)
    b = self.set_value(x * 2 + 2)
    if a == None and b == None:
      self.value[x] = None
    elif a == None:
      self.value[x] = b
    elif b == None:
      self.value[x] = a
    else:
      self.value[x] = a + b
    return self.value[x]

  def update(self, i, x):
    target = self.iter_size + i - 1
    while target >= 0:
      self.value[target] += x
      target = (target - 1) // 2

  def query(self, x, left, right):
    x_left, x_right = self.range[x]
    if right < x_left or x_right < left:
      #print("A")
      return 0
    if x_left < left and right < x_right:
      #print("B")
      return self.query(x * 2 + 1, left, right) + self.query(x * 2 + 2, left, right)
    if x_left < left and x_right <= right:
      #print("C")
      return self.query(x * 2 + 1, left, right) + self.query(x * 2 + 2, left, right)
    if left <= x_left and right < x_right:
      #print("D")
      return self.query(x * 2 + 1, left, right) + self.query(x * 2 + 2, left, right)
    if left <= x_left and x_right <= right:
      #print("E")
      return self.value[x]

  def print_tree(self):
    print(self.value)
    print(self.range)

n, q = map(int, input().split())
tree = TemplateTree([0] * n)

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

Submission status: Accepted

Solution code:
class TemplateTree:
  def __init__(self, iterable):
    self.iter_size = self.get_size(iterable)
    self.size = self.iter_size * 2 - 1
    self.value = [None] * self.size
    for i, v in enumerate(iterable):
      self.value[self.iter_size + i - 1] = v
    self.set_value(0)
    self.range = [None] * self.size
    self.set_range(0, 0, self.iter_size - 1)
  
  def get_size(self, iterable):
    ret = 1
    x = len(iterable)
    while ret < x:
      ret *= 2
    return ret
  
  def set_range(self, x, left, right):
    self.range[x] = (left, right)
    if left != right:
      self.set_range(x * 2 + 1, left, (right + left) // 2)
      self.set_range(x * 2 + 2, (right + left) // 2 + 1, right)

  def set_value(self, x):
    if x >= self.iter_size - 1:return self.value[x]
    a = self.set_value(x * 2 + 1)
    b = self.set_value(x * 2 + 2)
    if a == None and b == None:
      self.value[x] = None
    elif a == None:
      self.value[x] = b
    elif b == None:
      self.value[x] = a
    else:
      self.value[x] = a + b
    return self.value[x]

  def update(self, i, x):
    target = self.iter_size + i - 1
    while target >= 0:
      self.value[target] += x
      target = (target - 1) // 2

  def query(self, x, left, right):
    x_left, x_right = self.range[x]
    if right < x_left or x_right < left:
      return 0
    if left <= x_left and x_right <= right:
      return self.value[x]

    return self.query(x * 2 + 1, left, right) + self.query(x * 2 + 2, left, right)

  def print_tree(self):
    print(self.value)
    print(self.range)

n, q = map(int, input().split())
tree = TemplateTree([0] * n)

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

Submission status: Accepted

Solution code:
import sys

def initialize(N):
    i = 1
    while i < N:
        i *= 2
    return [0] * (2 * i - 1), i

def add(i, x, L, d):
    K = i + d - 1
    L[K] += x
    while K > 0:
        K = (K-1)//2
        L[K] += x

def getSum(s, t, index, l, r, L): 
    if r <= s or t <= l: return 0
    elif s <= l and r <= t: return L[index]
    else:
        sumL = getSum(s, t, 2 * index + 1, l, (l+r)//2, L)
        sumR = getSum(s, t, 2 * index + 2, (l+r)//2, r, L)
        return sumL + sumR

F = sys.stdin
N, Q = map(int, F.readline().strip("\n").split(" "))
SegTree, d = initialize(N)
for _ in range(Q):
    com, x, y = map(int, F.readline().strip("\n").split(" "))
    if com == 0: add(x-1, y, SegTree, d)
    elif com == 1:
        print(getSum(x-1, y, 0, 0, d, SegTree))

Submission status: Accepted

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

import sys

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 BIT:
    # n+1で初期化すること
    def __init__(self, n):
        # 0-indexed
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    # [0, i]を合計する
    def sum(self, i):
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    # 値の追加：添字, 値
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    # 区間和の取得 [l, r)
    def get(self, l, r=None):
        # 引数が1つなら一点の値を取得
        if r is None: r = l+1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

N,Q=MAP()
bit=BIT(N+1)
for _ in range(Q):
    com,x,y=MAP()
    if com==0:
        bit.add(x, y)
    else:
        print(bit.get(x, y+1))

Submission status: Accepted

Solution code:
import operator


class SegmentTree:
    # http://tsutaj.hatenablog.com/entry/2017/03/29/204841
    def __init__(self, size, fn=operator.add, default=0):
        """
        :param int size:
        :param callable fn: 区間に適用する関数。引数を 2 つ取る。min, max, operator.xor など
        """
        # size 以上である最小の 2 冪
        n = 1
        while n < size:
            n *= 2
        self._size = n
        self._tree = [default for _ in range(self._size * 2 - 1)]
        self._fn = fn

    def set(self, i, value):
        """
        i 番目に value を設定
        :param int i:
        :param int value:
        :return:
        """
        x = self._size - 1 + i
        self._tree[x] = value

        while x > 0:
            x = (x - 1) // 2
            self._tree[x] = self._fn(self._tree[x * 2 + 1], self._tree[x * 2 + 2])

    def add(self, i, value):
        """
        もとの i 番目と value に fn を適用したものを i 番目に設定
        :param int i:
        :param int value:
        :return:
        """
        x = self._size - 1 + i
        self.set(i, self._fn(self._tree[x], value))

    def get(self, from_i, to_i, k=0, L=None, r=None):
        """
        [from_i, to_i) に fn を適用した結果を返す
        :param int from_i:
        :param int to_i:
        :param int k: self._tree[k] が、[L, r) に fn を適用した結果を持つ
        :param int L:
        :param int r:
        :return:
        """
        L = 0 if L is None else L
        r = self._size if r is None else r

        if from_i <= L and r <= to_i:
            return self._tree[k]

        if to_i <= L or r <= from_i:
            return None

        ret_L = self.get(from_i, to_i, k * 2 + 1, L, (L + r) // 2)
        ret_r = self.get(from_i, to_i, k * 2 + 2, (L + r) // 2, r)
        if ret_L is None:
            return ret_r
        if ret_r is None:
            return ret_L
        return self._fn(ret_L, ret_r)

    def __len__(self):
        return self._size


N, Q = list(map(int, input().split()))
com, X, Y = zip(*[input().split() for _ in range(Q)])
X = list(map(int, X))
Y = list(map(int, Y))

if __name__ == '__main__':
    st = SegmentTree(size=N + 1, fn=operator.add, default=0)
    for c, x, y in zip(com, X, Y):
        if c == '0':
            st.add(x, y)
        if c == '1':
            print(st.get(x, y + 1))

Submission status: Accepted

Solution code:
import sys
import itertools

class RSQ:
    def __init__(self, n):
        self.sz = 1
        self.inf = (1 << 31) - 1
        while self.sz <= n: self.sz = self.sz << 1
        self.dat = [0] * (2 * self.sz - 1)
    
    def update(self, idx, x):
        idx += self.sz - 1
        self.dat[idx] += x
        while idx > 0:
            idx = (idx - 1) >> 1
            self.dat[idx] += x
            
    def query(self, a, b):
        return self.query_help(a, b, 0, 0, self.sz)
            
    def query_help(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        elif a <= l and r <= b:
            return self.dat[k]
        else:
            return self.query_help(a, b, 2 * k + 1, l, (l + r)>>1) + \
                    self.query_help(a, b, 2 * k + 2, (l + r) >> 1, r)
    
    
if __name__ == '__main__':
    line = sys.stdin.readline()
    n, q = line.split()
    n, q = int(n), int(q)
    rmq = RSQ(n)
    
    for i in range(q):
        line = sys.stdin.readline()
        op, a, b = line.split()
        op, a, b = int(op), int(a), int(b)
        if op == 0: 
            rmq.update(a, b)
        else: 
            sys.stdout.write(str(rmq.query(a, b + 1)) + '\n')

Submission status: Accepted

Solution code:
class RangeSumQuery(object):

    def __init__(self, size):
        self.size = 1
        while self.size <= size:
            self.size *= 2
        self.data = [0] * (self.size*2+2)

    def add(self, idx, value):
        k = idx + self.size - 1
        self.data[k] += value
        while k > 0:
            k = (k - 1) / 2
            self.data[k] += value

    def get_sum(self, start, end):
        def query(k, left, right):
            if right <= start or end <= left:
                return 0
            if start <= left and right <= end:
                return self.data[k]
            vl = query(k*2+1, left, (left+right)/2)
            vr = query(k*2+2, (left+right)/2, right)
            return sum([vl, vr])
        return query(0, 0, self.size)


def main():
    n, q = map(int, raw_input().split())
    rsq = RangeSumQuery(n)
    for _ in xrange(q):
        com, x, y = map(int, raw_input().split())
        if com == 0:
            rsq.add(x, y)
        else:
            print rsq.get_sum(x, y+1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class RangeSumQuery(object):

    def __init__(self, size):
        self.size = 1
        while self.size <= size:
            self.size *= 2
        self.data = [0] * (self.size*2-1)

    def add(self, idx, value):
        k = idx + self.size - 1
        self.data[k] += value
        while k > 0:
            k = (k - 1) / 2
            self.data[k] += value

    def get_sum(self, start, end):
        def query(k, left, right):
            if right <= start or end <= left:
                return 0
            if start <= left and right <= end:
                return self.data[k]
            vl = query(k*2+1, left, (left+right)/2)
            vr = query(k*2+2, (left+right)/2, right)
            return vl + vr
        return query(0, 0, self.size)


def main():
    n, q = map(int, raw_input().split())
    rsq = RangeSumQuery(n)
    for _ in xrange(q):
        com, x, y = map(int, raw_input().split())
        if com == 0:
            rsq.add(x, y)
        else:
            print rsq.get_sum(x, y+1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class RangeSumQuery(object):

    def __init__(self, size):
        self.size = 1
        while self.size <= size:
            self.size *= 2
        self.data = [0 for _ in xrange(self.size*2-1)]

    def add(self, idx, value):
        k = idx + self.size - 1
        self.data[k] += value
        while k > 0:
            k = (k - 1) / 2
            self.data[k] += value

    def get_sum(self, start, end):
        def query(k, left, right):
            if right <= start or end <= left:
                return 0
            if start <= left and right <= end:
                return self.data[k]
            vl = query(k*2+1, left, (left+right)/2)
            vr = query(k*2+2, (left+right)/2, right)
            return vl + vr
        return query(0, 0, self.size)


def main():
    n, q = map(int, raw_input().split())
    rsq = RangeSumQuery(n)
    for _ in xrange(q):
        com, x, y = map(int, raw_input().split())
        if com == 0:
            rsq.add(x, y)
        else:
            print rsq.get_sum(x, y+1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
class segment_tree:
    
    # self.table is 1-indexed
    # math.log2 not implemented 3.2.3
    def __init__(self, dat, query, default=0):
        self.offset = 2 ** math.ceil(math.log(len(dat), 2))
        self.table = [default] * self.offset + dat + [default] * (self.offset - len(dat))
        self.query = query
        for i in reversed(range(1, self.offset)):
            self.table[i] = self.query((self.table[2 * i], self.table[2 * i + 1]))

    # [l, r] closed-interval
    def find(self, l, r):
        return self.query(self.__range(l,r))

    def __range(self, l, r):
        l += self.offset
        r += self.offset
        while l <= r:
            if l & 1:
                yield self.table[l]
                l += 1
            l >>= 1
            if r & 1 == 0:
                yield self.table[r]
                r -= 1
            r >>= 1
        
    def update(self, i, x, function=lambda a, b:b):
        i += self.offset
        self.table[i] = function(self.table[i], x)
        while 1 < i:
            i >>= 1
            self.table[i] = self.query((self.table[2 * i], self.table[2 * i + 1]))

from sys import stdin
readline = stdin.readline


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

rmq = segment_tree([0] * n, sum, default=0)
from operator import add
function = (lambda x, y:rmq.update(x - 1, y, add), lambda x, y:print(rmq.find(x - 1, y - 1)))
for com, x, y in (map(int, readline().split()) for _ in range(q)):
    function[com](x, y)

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, size):
        self.size = size
        self.bit = [0] * (size + 1)

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

    # sum [i, j)
    def sum_sec(self, i, j):
        return self.sum(j) - self.sum(i)

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

n, q = map(int, raw_input().split())
bit = BIT(n)
for i in xrange(q):
    c, x, y = map(int, raw_input().split())
    if c == 0: bit.add(x - 1, y)
    else: print bit.sum_sec(x - 1, y)

Submission status: Accepted

Solution code:
import math
class FenwickTree:
    """
    FenwickTree(Binary Indexed Tree)
    total number: n
    queries:
    1. add(i, val): add val to i-th value 
    2. sum(n): sum(bit[0] + ... + bit[n-1])
    complexity: O(log n)

    Self-balancing binary search tree or Segment Tree can do the same, it takes longer to program and complexity also increases.
    Thanks: http://hos.ac/slides/20140319_bit.pdf
    
    used in ARC031 C, indeednow finalB E
    """
    def __init__(self, a_list):
        # 0-indexed
        self.N = len(a_list)
        self.bit = a_list[:]
        for _ in range(N, 1<<(math.ceil(math.log(N, 2)))): 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

N, Q = map(int, input().split())
bit = FenwickTree([0]*N)
for _ in range(Q):
    com, x, y = map(int, input().split())
    if com == 0:
        bit.add(x-1, y)
    elif com == 1:
        print(bit.sum(y-1) - bit.sum(x-2))

Submission status: Accepted

Solution code:
from math import sqrt, ceil

n, q = map(int, input().split())
unit = ceil(sqrt(n))

l = [(0, [0] * unit) for _ in range(unit)]

while q:
    op, s, t = map(int, input().split())
    s -= 1
    sd, sm = s // unit, s % unit
    if op:
        t -= 1
        td, tm = t // unit, t % unit
        if sd == td:
            print(sum(l[sd][1][sm:tm + 1]))
        else:
            unit_sum = sum((tup[0] for tup in l[sd + 1:td]))
            s_sum = sum(l[sd][1][sm:])
            t_sum = sum(l[td][1][:tm + 1])
            print(unit_sum + s_sum + t_sum)
    else:
        tup = l[sd]
        tup[1][sm] += t
        l[sd] = (tup[0] + t, tup[1])
    q -= 1

Submission status: Accepted

Solution code:
#!/usr/bin/python3
import math

# main
n, q = map(int, input().split())
b_size = math.ceil(math.sqrt(n))
b_len = math.ceil(n/b_size)
a = [0 for i in range(n)]
b = [min(a[b_size * i:b_size * (i + 1)]) for i in range(b_len)]
for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        x -= 1
        # update
        a[x] += y
        # update b
        index = x // b_size
        #b[index] = min(a[index * b_size:(index + 1) * b_size])
        b[index] += y

    else:
        x -= 1
        y -= 1
        # find
        target = []
        x_index = x // b_size
        y_index = y // b_size
        x_mod = x % b_size
        y_mod = y % b_size
        if x_index == y_index:
            target.extend(a[x:y + 1])
        else:
            if x_mod == 0:
                target.append(b[x_index])
            else:
                target.extend(a[x:(x_index + 1) * b_size])

            if y_mod == b_size - 1:
                target.append(b[y_index])
            else:
                target.extend(a[y_index * b_size:y + 1])

            if x_index + 1 <= y_index - 1:
                target.append(sum(b[x_index + 1 : y_index]))
        print(sum(target))

Submission status: Accepted

Solution code:
N, Q = [int(x) for x in raw_input().split()]

class Node:

    def __init__(self, x, y):
        self.value = 0
        self.x = x
        self.y = y
        self.l = self.r = None

        if y - x > 1:
            mid = (x + y) / 2
            self.l = Node(x, mid)
            self.r = Node(mid, y)

    def add(self, i, x):
        if self.x <= i < self.y:
            self.value += x
            if self.l:
                self.l.add(i, x)
            if self.r:
                self.r.add(i, x)

    def sum(self, x, y):
        if y <= self.x or self.y <= x:
            return 0
        if x <= self.x and self.y <= y:
            return self.value
        return self.l.sum(x, y) + self.r.sum(x, y)

t = Node(0, N)

for _ in xrange(Q):
    com, x, y = [int(s) for s in raw_input().split()]
    if com == 0:
        t.add(x-1, y)
    if com == 1:
        print t.sum(x-1, y)

Submission status: Accepted

Solution code:
class BIT(object):

    def __init__(self, size, init_data=None):
        self.size = size
        if init_data is None:
            init_data = [0] * (size + 1)
        self.data = init_data

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

    def add(self, idx, value):
        while idx <= self.size:
            self.data[idx] += value
            idx += idx & -idx

if __name__ == "__main__":
    n, q = list(map(int, input().split()))
    bit = BIT(n)
    for _ in range(q):
        com, x, y = list(map(int, input().split()))
        if com == 0:
            bit.add(x, y)
        else:
            print(bit.sum(y)-bit.sum(x-1))