Problem:


Score : 100 points

Problem Statement

You are given an array a_0, a_1, ..., a_{N-1} of length N. Process Q queries of the following types.

0 p x: a_p \gets a_p + x

1 l r: Print \sum_{i = l}^{r - 1}{a_i}.

Constraints

1 \leq N, Q \leq 500,000

0 \leq a_i, x \leq 10^9

0 \leq p < N

0 \leq l_i < r_i \leq N

All values in Input are integer.

Input

Input is given from Standard Input in the following format:

N Q
a_0 a_1 ... a_{N - 1}
\textrm{Query}_0
\textrm{Query}_1
:
\textrm{Query}_{Q - 1}

Output

For each query of the latter type, print the answer.

Sample Input 1

5 5
1 2 3 4 5
1 0 5
1 2 4
0 3 10
1 0 5
1 0 3

Sample Output 1

15
7
25
6



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


Sample output:
15
7
25
6

Submission status: Accepted

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

class BIT:
	"""
	<Attention> 0-indexed.
	query ... return the sum [0 to m]
	sum ... return the sum [a to b]
	sumall ... return the sum [all]
	add ... 'add' number to element (be careful that it doesn't set a value.)
	search ... the sum version of bisect.right
	output ... return the n-th element
	listout ... return the BIT list
	"""
	def query(self, m):
		res = 0
		while m > 0:
			res += self.bit[m]
			m -= m&(-m)
		return res
	
	def sum(self, a, b):
		return self.query(b)-self.query(a)
	
	def sumall(self):
		bitlen = self.bitlen-1
		return self.query(bitlen)

	def add(self, m, x):
		m += 1
		bitlen = len(self.bit)
		while m <= bitlen-1:
			self.bit[m] += x
			m += m&(-m)
		return
	
	def search(self, a):
		tmpsum = 0
		i = 0
		k = (self.bitlen-1).bit_length()
		while k >= 0:
			tmpk = 2**k
			if i+tmpk <= self.bitlen-1:
				if tmpsum + self.bit[i+tmpk] < a:
					tmpsum += self.bit[i+tmpk]
					i += tmpk
			k = k - 1
		return i+1
	
	def output(self, a):
		return self.query(a+1)-self.query(a)
	
	def listout(self):
		return self.bit
	
	def __init__(self, a):
		self.bitlen = len(a)+1
		self.bit = [0]*(len(a)+1)
		for i, j in enumerate(a):
			self.add(i, j)

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

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

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
BIT = [0] * (n + 1)
def add(i, x):
    while i <= n:
        BIT[i] += x
        i += i & -i
def query(i):
    s = 0
    while i > 0:
        s += BIT[i]
        i -= i & -i
    return s
a = list(map(int, input().split()))
for i in range(n):
    add(i + 1, a[i])
for i in range(q):
    x, y, z = map(int, input().split())
    if x == 0:
        add(y + 1, z)
    else:
        print(query(z) - query(y))

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit, i8, jitclass
import sys

spec = [
    ("size", i8),
    ("tree", i8[:])
]


@jitclass(spec)
class Bit:
    def __init__(self, n, arr):
        self.size = n
        self.tree = np.array([0] + arr, np.int64)
        for i in range(1, n+1):
            self.tree[i + 1 | i + 2] += self.tree[i]

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

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

    def range_sum(self, l, r):
        return self.sum(r) - self.sum(l)


def main():
    n, q = map(int, sys.stdin.buffer.readline().split())
    bit = Bit(n, list(map(int, sys.stdin.buffer.readline().split())))
    for x in sys.stdin.buffer.readlines():
        q, p, x = map(int, x.split())
        if q:
            print(bit.range_sum(p, x))
        else:
            bit.add(p+1, x)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit, i8, jitclass
import sys

spec = [
    ("size", i8),
    ("tree", i8[:])
]


@jitclass(spec)
class Bit:
    def __init__(self, n, arr):
        self.size = n
        self.tree = np.array([0] + arr, np.int64)
        for i in range(1, n+1):
            self.tree[i + (i & -i)] += self.tree[i]

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

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

    def range_sum(self, l, r):
        return self.sum(r) - self.sum(l)


def main():
    n, q = map(int, sys.stdin.buffer.readline().split())
    bit = Bit(n, list(map(int, sys.stdin.buffer.readline().split())))
    for x in sys.stdin.buffer.readlines():
        q, p, x = map(int, x.split())
        if q:
            print(bit.range_sum(p, x))
        else:
            bit.add(p+1, x)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys


class Bit:
    def __init__(self, n, arr):
        self.size = n
        self.tree = [0] + arr
        for i in range(1, n+1):
            if i + (i & -i) < n+1:
                self.tree[i + (i & -i)] += self.tree[i]

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

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

    def range_sum(self, l, r):
        return self.sum(r) - self.sum(l)


def main():
    n, q = map(int, sys.stdin.buffer.readline().split())
    bit = Bit(n)
    bit.build(map(int, sys.stdin.buffer.readline().split()))
    for x in sys.stdin.buffer.readlines():
        q, p, x = map(int, x.split())
        if q:
            print(bit.range_sum(p, x))
        else:
            bit.add(p+1, x)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys


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 add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


def main():
    # 使用例
    n, q = map(int, sys.stdin.buffer.readline().split())
    bit = Bit(n+1)
    a = list(map(int, sys.stdin.buffer.readline().split()))
    for i in range(1, n+1):
        bit.add(i, a[i])
    print(bit.tree)
    for x in sys.stdin.buffer.readlines():
        q, p, x = map(int, x.split())
        if q:
            print(bit.sum(x) - bit.sum(p))
        else:
            bit.add(p, x)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# distutils: language=c++
# distutils: include_dirs=[/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False
cimport numpy as np
cdef extern from "<atcoder/fenwicktree>" namespace "atcoder" nogil:
    cdef cppclass fenwick_tree[T]:
        fenwick_tree(int n)
        void add(int p, T x)
        T sum(int l, int r)

cdef class FenwickTree:
    cdef fenwick_tree[long long] *_thisptr
    def __cinit__(self, np.ndarray[long, ndim=1] array):
        cdef int N = array.size
        self._thisptr = new fenwick_tree[long long](N)
        for i in range(N):
            self.add(i, array[i])
    cpdef void add(self, int p, long long x):
        self._thisptr.add(p, x)
    cpdef long long sum(self, int l, int r):
        return self._thisptr.sum(l, r)

Submission status: Runtime Error

Solution code:

code = """

# distutils: language=c++
# distutils: include_dirs=[/home/USERNAME/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False


cimport numpy as np
cdef extern from "<atcoder/fenwicktree>" namespace "atcoder" nogil:
    cdef cppclass fenwick_tree[T]:
        fenwick_tree(int n)
        void add(int p, T x)
        T sum(int l, int r)

ctypedef np.int DTYPE_t

cdef class FenwickTree:
    cdef fenwick_tree[long long] *_thisptr
    def __cinit__(self, np.ndarray[DTYPE_t, ndim=1] array):
        cdef int N = array.size()
        self._thisptr = new fenwick_tree[long long](N)
        for i in range(N):
            self.add(i, array[i])
    cpdef void add(self, int p, long long x):
        self._thisptr.add(p, x)
    cpdef long long sum(self, int l, int r):
        return self._thisptr.sum(l, r)
"""


import os, sys, getpass

if sys.argv[-1] == 'ONLINE_JUDGE':
    code = code.replace("USERNAME", getpass.getuser())
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
    sys.exit(0)


from atcoder import FenwickTree
import numpy as np

N,Q = list(map(int,input().split()))
bit = FenwickTree(np.array(list(map(int,input().split())), dtype=np.int))

for i in range(Q):
    a,b,c = list(map(int,input().split()))
    if a==0:
        bit.add(b,c)
    else:
        print(bit.sum(b,c))

Submission status: Runtime Error

Solution code:

code = """

# distutils: language=c++
# distutils: include_dirs=[/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False


cdef extern from "<atcoder/fenwicktree>" namespace "atcoder":
    cdef cppclass fenwick_tree[T]:
        fenwick_tree(int n)
        void add(int p, T x)
        T sum(int l, int r)

cdef class FenwickTree:
    cdef fenwick_tree[long long] *_thisptr
    def __cinit__(self, int n):
        self._thisptr = new fenwick_tree[long long](n)
    cpdef void add(self, int p, long long x):
        self._thisptr.add(p, x)
    cpdef long long sum(self, int l, int r):
        return self._thisptr.sum(l, r)
"""


import os,sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')


from atcoder import FenwickTree

readline = sys.stdin.buffer.readline

N, Q = list(map(int, readline().split()))
ft = FenwickTree(N)

A = list(map(int, readline().split()))

for i, a in enumerate(A):
    ft.add(i, a)

for i in range(N):
    a, b, c = list(map(int, readline().split()))
    if a == 0:
        ft.add(b, c)
    else:
        print(ft.sum(b, c))

Submission status: Runtime Error

Solution code:
def p(k: int):
    ans = 0
    for i in range(20):
        if k % (1<<i) == 0:
            ans = i
        else:
            break
    return ans

def sum_f(k: int, tree: list):
    s = 0
    while k >= 1:
        s += tree[k]
        k -= k&-k
    return s

def add(k: int, x: int, tree: list):
    while k <= len(tree):
        tree[k] += x
        k += k&-k

def main():
    n, q = map(int, input().split())
    a = [0] + list(map(int, input().split()))
    fenwick = a.copy()
    for i in range(1, len(fenwick)):
        fenwick[i] = sum(fenwick[i-p(i):i+1])
    # print(fenwick)
    for _ in range(q):
        i, j, k = map(int, input().split())
        if i:
            print(sum_f(k, fenwick) - sum_f(j, fenwick))
        else:
            add(j, k, fenwick)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vl2;
const bool multiple_queries = false;
#define rep(i, n) for(ll i = 0; i < (n) ; ++i)
#define For(i, a, b) for(ll i = (a); i < (b) ; ++i)
#define revrep(i, n) for(ll i = (n) - 1; i >= 0 ; --i)
#define revFor(i, b, a) for(ll i = (b) - 1; i >= (a) ; --i)
#define all(v) v.begin(), v.end()
#define rall(v) (v).rbegin(), (v).rend()
#define popcount(i) __builtin_popcountl((i))
#define substring(s, start, end) s.substr((start), (end) - (start) + 1)

struct BinaryIndexedTree{
  ll n, ini, M; vl dat;
  BinaryIndexedTree(ll n, ll ini = 0):
    dat(n + 1, ini), n(n), ini(ini){M = 1; while (M <= n) M <<= 1;};

  //       x: 1001 1010  1100 1011 1101  1111
  // x & - x: 0001 0010  0100 0001 0001  0001
  //      ->: 1010 1100 10000 1100 1100 10000

  ll update_func(ll val, ll d){
    // if maximum -> max(val, dat)
    // return max(val, d);
    // if cumulative sum
    return val + d;
  }

  ll query(ll i){
    /*
    v[0] + v[1] + ... + v[i]
    e.g.) i = 10101
    itr1. 10101 -> 10100
    itr2. 10100 -> 10000
    itr3. 10000 -> 00000 (break)
    */

    if (i < 0) return ini;
    ll ret = 0;
    for (ll j = i; j >= 0; j = (j & (j + 1)) - 1){
      ret = update_func(ret, dat[j]);
    }
    return ret;
}

  ll query(ll l, ll r){
    // a[l] + a[l + 1] + ... + a[r - 1] + a[r]
    return query(r) - query(l - 1);
  }

  ll lower_bound(ll key){
    //v[0] + v[1] + ... + v[left - 1] < key <= v[0] + v[1] + ... + v[left]
    if (key <= 0) return 0;
    ll left = 0, right = 1;
    while(right <= n) right <<= 2;

    for (ll i = right; i > 0; i /= 2){
      if (left + i <= n && dat[left + i - 1] < key){
        key -= dat[left + i - 1];
        left += i;
      }
    }
    return left;
  }

  void update(ll i, ll val){
    /*
    e.g.) i = 10101, n = 11111
    itr1. i: 10101, i+1: 10110 -> 10111
    itr2. i: 10111, i+1: 11000 -> 11111 (break)
    */
    if (i < 0) return;
    for(ll j = i; j < n; j |= j + 1){
      dat[j] = update_func(val, dat[j]);
    }
  }
};

template<typename T>
void read_vector(ll n, vector<T>& v, ll offset = 0){
  v.resize(n);
  rep(i, n){
    cin >> v[i];
    if (offset) v[i] += offset;
  }
}

void solve(){
  ll n, Q;
  cin >> n >> Q;
  vl as;
  read_vector(n, as);
  BinaryIndexedTree bit(n);
  rep(i, n) bit.update(i, as[i]);
  rep(i, Q){
    ll mode; cin >> mode;
    if (mode){
      ll l, r; cin >> l >> r;
      cout << bit.query(l, r - 1) << endl;
    }else{
      ll p, x; cin >> p >> x;
      bit.update(p, x);
    }
  }
}

void test(ll num = 0, bool verbose = false){
  rep(i, max(1LL, num)){
    ll t = clock();
    if (verbose) cout << "\n#####" << " " << i + 1 << " " << "#####" << " " << "\n## Answer ##\n";
    solve();
    if (verbose) {cout << "\nElapsed Time:" << " " << 1000.0 * (clock() - t) / CLOCKS_PER_SEC << " " << "[ms]" << endl;}
  }
}

int main(void){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  #ifdef _LOCAL
    test(6, true);
  #else
    ll t = 0;
    if (multiple_queries) cin >> t;
    test(t, false);
  #endif
  return 0;
}

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
n,q=map(int,input().split())
a=list(map(int,input().split()))
bit=[0]*(2*n+10)
def bit_update(x,v):
    while x<size:
        bit[x]+=v
        x+=(x&-x)
def bit_sum(n):
    s=0
    if n==0:return 0
    x=n
    while x>0:
        s+=bit[x]
        x-=(x&-x)
    return s
for i,j in enumerate(a,1):
    bit_update(i,j)
for i in range(q):
    a,b,c=map(int,input().split())
    if a==0:
        bit_update(b+1,c)
    else:
        print(bit_sum(c)-bit_sum(b))

Submission status: Runtime Error

Solution code:
n,q=map(int,input().split())
a=list(map(int,input().split()))
size=(1<<18)+1
bit=[0]*size
def bit_update(x,v):
    while x<size:
        bit[x]+=v
        x+=(x&-x)
def bit_sum(n):
    s=0
    if n==0:return 0
    x=n
    while x>0:
        s+=bit[x]
        x-=(x&-x)
    return s
for i,j in enumerate(a,1):
    bit_update(i,j)
for i in range(q):
    a,b,c=map(int,input().split())
    if a==0:
        bit_update(b+1,c)
    else:
        print(bit_sum(c)-bit_sum(b))

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
code = r"""
# distutils: language=c++
# distutils: include_dirs=/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include
# cython: boundscheck=False
# cython: wraparound=False
from libcpp cimport bool
from libcpp.vector cimport vector
cdef extern from "/opt/atcoder-stl/atcoder/fenwicktree.hpp" namespace "atcoder":
    cdef cppclass fenwick_tree[T]:
        fenwick_tree(int)
        void add(int, T)
        T sum(int, int)

from libc.stdio cimport scanf, printf
cdef int i
cdef int N, Q
cdef int t, u, v
scanf("%d%d", &N, &Q)
cdef fenwick_tree[long long] *ft = new fenwick_tree[long long](N);
for i in range(Q):
    scanf("%d%d%d", &t, &u, &v)
    if t == 0:
        ft.add(u, <long long> v)
    else:
        printf("%lld\n", ft.sum(u, v))
"""
import os
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Runtime Error

Solution code:
code = r"""
# distutils: language=c++
# distutils: include_dirs=/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include
# cython: boundscheck=False
# cython: wraparound=False
from libcpp cimport bool
from libcpp.vector cimport vector
cdef extern from "/opt/atcoder-stl/atcoder/fenwicktree.hpp" namespace "atcoder":
    cdef cppclass fenwick_tree[T]:
        fenwick_tree(int)
        void add(int, T)
        T sum(int int)

from libc.stdio cimport scanf, printf
cdef int i
cdef int N, Q
cdef int t, u, v
scanf("%d%d", &N, &Q)
cdef fenwick_tree[long long] *ft = new fenwick_tree[long long](N);
for i in range(Q):
    scanf("%d%d%d", &t, &u, &v)
    if t == 0:
        ft.add(u, <long long> v)
    else:
        printf("%lld\n", ft.sum(u, v))
"""
import os
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Runtime Error

Solution code:
code = r"""
# distutils: language=c++
# distutils: include_dirs=/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include
# cython: boundscheck=False
# cython: wraparound=False
from libcpp cimport bool
from libcpp.vector cimport vector
cdef extern from "/opt/atcoder-stl/atcoder/fenwicktree.hpp" namespace "atcoder":
    cdef cppclass fenwick_tree[T]:
    	fenwick_tree(int)
        void add(int, T)
        T sum(int int)

from libc.stdio cimport scanf, printf
cdef int i
cdef int N, Q
cdef int t, u, v
scanf("%d%d", &N, &Q)
cdef fenwick_tree[long long] *ft = new fenwick_tree[long long](N);
for i in range(Q):
    scanf("%d%d%d", &t, &u, &v)
    if t == 0:
    	ft.add(u, <long long> v)
    else:
        printf("%lld\n", ft.sum(u, v))
"""
import os
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Runtime Error

Solution code:
code = r"""
# distutils: language=c++
# distutils: include_dirs=/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include
# cython: boundscheck=False
# cython: wraparound=False
from libcpp cimport bool
from libcpp.vector cimport vector
cdef extern from "/opt/atcoder-stl/atcoder/fenwicktree.hpp" namespace "atcoder":
    cdef cppclass fenwick_tree[T]:
    	fenwick_tree(int)
        void add(int, T)
        T sum(int int)

from libc.stdio cimport scanf, printf
cdef int i
cdef int N, Q
cdef int t, u, v
scanf("%d%d", &N, &Q)
cdef fenwick_tree[long long] *ft = new fenwick_tree[long long](N);
for i in range(Q):
    scanf("%d%d%d", &t, &u, &v)
    if t == 0:
    	ft.add(u, v)
    else:
        printf("%lld\n", ft.sum(u, v))
"""
import os
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Runtime Error

Solution code:
code = r"""
# distutils: language=c++
# distutils: include_dirs=/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include
# cython: boundscheck=False
# cython: wraparound=False
from libcpp cimport bool
from libcpp.vector cimport vector
cdef extern from "/opt/atcoder-stl/atcoder/fenwicktree.hpp" namespace "atcoder":
    cdef cppclass fenwick_tree[T]:
    	fenwick_tree(int)
        void add(int, T)
        T sum(int int)

from libc.stdio cimport scanf, printf
cdef int i
cdef int N, Q
cdef int t, u, v
scanf("%d%d", &N, &Q)
cdef fenwick_tree[long long] *ft = new fenwick_tree[long long](N);
for i in range(Q):
    scanf("%d%d%d", &t, &u, &v)
    if t == 0:
    	ft.add(u, v)
    else:
        printf("%lld\n", d.sum(u, v))
"""
import os
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Runtime Error

Solution code:
code = r"""
# distutils: language=c++
# distutils: include_dirs=/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include
# cython: boundscheck=False
# cython: wraparound=False
from libcpp cimport bool
from libcpp.vector cimport vector
cdef extern from "/opt/atcoder-stl/atcoder/fenwicktree.hpp" namespace "atcoder":
    cdef cppclass fenwick_tree[T]:
    	fenwick_tree(int)
        void add(int, T)
        T sum(int int)

from libc.stdio cimport scanf, printf
cdef int i
cdef int N, Q
cdef int t, u, v
scanf("%d%d", &N, &Q)
cdef fenwick_tree[long long] *ft = new fenwick_tree[long long](N);
for i in range(Q):
    scanf("%d%d%d", &t, &u, &v)
    if t == 0:
    	ft.add(u, v);
        d.merge(u, v)
    else:
        printf("%d\n", d.sum(u, v))
"""
import os
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve