Problem:


Range Add Query (RAQ)

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

  
add(s, t, x): add x to as, as+1, ..., at.

  
get(i): output the value of ai.

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

Input

n q
query1
query2
:
queryq

  In the first line, n (the number of elements in A) and q (the number of queries) are given. Then, ith query queryi is given in the following format:

0 s t x 

  or

1 t

  The first digit represents the type of the query. '0' denotes add(s, t, x) and '1' denotes get(i).

Output

For each get operation, print the value.

Constraints

1 ≤ n ≤ 100000

1 ≤ q ≤ 100000

  1 ≤ s ≤ t ≤ n

  1 ≤ i ≤ n

  0 ≤ x ≤ 1000
  

Sample Input 1

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

Sample Output 1

3
5

Sample Input 2

4 3
1 2
0 1 4 1
1 2

Sample Output 2

0
1



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


Sample output:
3
5

Submission status: Accepted

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

class SegmentTreeDual():
    def __init__(self,arr,op=lambda x,y:y if y != -1 else x,ie=-1):
        self.h = (len(arr)-1).bit_length()
        self.n = 2**self.h
        self.ie = ie
        self.op = op
        self.val = [ie for _ in range(len(arr))]
        self.laz = [ie for _ in range(2*self.n)]
        for i in range(len(arr)):
            self.val[i] = arr[i]
    def propagate(self,k):
        if self.laz[k] == self.ie:
            return
        if self.n <= k:
            self.val[k-self.n] = self.op(self.val[k-self.n],self.laz[k])
            self.laz[k] = self.ie
        else:
            self.laz[(k<<1)] = self.op(self.laz[(k<<1)],self.laz[k])
            self.laz[(k<<1)+1] = self.op(self.laz[(k<<1)+1],self.laz[k])
            self.laz[k] = self.ie
    def update(self,left,right,f):
        left += self.n
        right += self.n
        for i in reversed(range(self.h+1)):
            self.propagate(left>>i)
        for i in reversed(range(self.h+1)):
            self.propagate((right-1)>>i)
        while right - left > 0:
            if right & 1:
                right -= 1
                self.laz[right] = self.op(self.laz[right],f)
            if left & 1:
                self.laz[left] = self.op(self.laz[left],f)
                left += 1
            left >>= 1
            right >>= 1
    def get(self,index):
        res = self.val[index]
        index += self.n
        while index:
            res = self.op(res,self.laz[index])
            index //= 2
        return res

N,Q = map(int,input().split())
A = [0 for _ in range(N)]
sg = SegmentTreeDual(A,lambda x,y:x+y,0)
ans = []

for _ in range(Q):
    q = list(map(int,input().split()))
    if q[0] == 0:
        s,t,x = q[1:]
        sg.update(s-1,t,x)
    else:
        i = q[1]
        ans.append(sg.get(i-1))

print('\n'.join(map(str,ans)))

Submission status: Accepted

Solution code:

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

class LazySegmentTree():
    def __init__(self, n):
        n_ = 1
        c_ = 0
        while n_ < n:
            n_ *= 2
            c_ +=1

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

    #伝播区間
    def getidx(self, l, r):
        L = (l + self.n) >> 1
        R = (r + self.n) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        for i in range(self.lv):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1; R >>=1

    #伝播
    def propagate(self,*ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if v is 0:
                continue
            self.lazy[2*i-1] += v
            self.arr[2*i-1] += v
            self.lazy[2*i] += v
            self.arr[2*i] += v
            self.lazy[i-1] = 0

    #[l, r] をxで更新
    def update(self,l,r,x):
        #[l, r)に変更
        r+=1
        *ids, = self.getidx(l,r)
        self.propagate(*ids)

        L = self.n + l; R = self.n + r
        while L < R:
            if R & 1:
                R -=1
                self.lazy[R-1] += x
                self.arr[R-1] += x
            if L & 1:
                self.lazy[L-1] += x
                self.arr[L-1] += x
                L += 1
            L >>= 1; R >>= 1

        for i in ids:
            self.arr[i-1] = func(self.arr[2*i-1], self.arr[2*i])

    #[l, r]のクエリに答える
    def query(self,l,r):
        #[l, r)に変更
        r+=1
        self.propagate(*self.getidx(l,r))
        L = self.n + l; R = self.n + r

        s = 0 #初期化！！！
        while L < R:
            if R & 1:
                R -=1
                s = func(s, self.arr[R-1])
            if L & 1:
                s = func(s, self.arr[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

#0-indexed なので1-からのときは−１する
import sys
input=sys.stdin.readline
n,q=map(int,input().split())
sg=LazySegmentTree(n)
for _ in range(q):
    l=list(map(int,input().split()))
    if l[0]==0:
        c,s,t,x=l
        sg.update(s-1,t-1,x)
    else:
        c,i=l
        print(sg.query(i-1,i-1))

Submission status: Accepted

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


class BIT():
    """区間加算、一点取得クエリをそれぞれO(logN)で答える
    add: 区間[l, r)にvalを加える
    get_val: i番目の値を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)


n, q = map(int, input().split())
query = [list(map(int, input().split())) for i in range(q)]
bit = BIT(n)

ans = []
for i in range(q):
    if query[i][0] == 0:
        _, l, r, x = query[i]
        bit.add(l-1, r, x)
    else:
        _, i = query[i]
        print(bit.get_val(i-1))

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class BIT2:
    """ 区間加算BIT(区間加算・区間合計取得) """

    def __init__(self, N):
        self.N = N
        self.data0 = [0] * N
        self.data1 = [0] * N

    def _add(self, data, k, x):
        while k < self.N:
            data[k] += x
            k += k & -k

    def _get(self, data, k):
        s = 0
        while k:
            s += data[k]
            k -= k & -k
        return s

    def add(self, l, r, x):
        """ 区間[l,r)に値xを追加 """

        self._add(self.data0, l, -x*(l-1))
        self._add(self.data0, r, x*(r-1))
        self._add(self.data1, l, x)
        self._add(self.data1, r, -x)

    def query(self, l, r):
        """ 区間[l,r)の和を取得 """

        return self._get(self.data1, r-1) * (r-1) + self._get(self.data0, r-1) \
             - self._get(self.data1, l-1) * (l-1) - self._get(self.data0, l-1)

N, Q = MAP()
bit = BIT2(N+1)

ans = []
for i in range(Q):
    cmd, *arg = MAP()
    if cmd == 0:
        s, t, x = arg
        bit.add(s, t+1, x)
    else:
        i, = arg
        ans.append(str(bit.query(i, i+1)))
print('\n'.join(ans))

Submission status: Accepted

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

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

    def update(self, beg: int, end: int, k: int, l: int, r: int, x: int) -> None:
        if (l == r or l == beg and r == end):  # noqa: E741
            self.val[k] += x
            return
        mid = (l + r) // 2
        if (end <= mid):
            self.update(beg, end, k * 2, l, mid, x)
        elif (beg > mid):
            self.update(beg, end, k * 2 + 1, mid + 1, r, x)
        else:
            self.update(beg, mid, k * 2, l, mid, x)
            self.update(mid + 1, end, k * 2 + 1, mid + 1, r, x)

    def find(self, k: int, l: int, r: int, idx: int) -> int:
        if (l == r):  # noqa: E741
            return self.val[k]
        mid = (l + r) // 2
        if (idx <= mid):
            return self.val[k] + self.find(k * 2, l, mid, idx)
        else:
            return self.val[k] + self.find(k * 2 + 1, mid + 1, r, idx)


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

    for _ in range(q):
        com, *v = map(lambda x: int(x), input().split())
        if (0 == com):
            raq.update(v[0], v[1], 1, 1, n, v[2])
        else:
            print(f"{raq.find(1, 1, n, v[0])}")

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#1:set
#1_A
"""
n,q = map(int, input().split(" "))
group = [[i] for i in range(n)]
key = [i for i in range(n)]
for i in range(q):
    com, x, y = map(int, input().split(" "))
    if com == 0:
        if key[x] != key[y]:
            v = key[y]
            group[key[x]] = group[key[x]] + group[key[y]]
            for j in group[v]:
                key[j] = key[x]
            group[v] = []
    if com == 1:
        if key[x] == key[y]:
            print(1)
        else:
            print(0)
"""

#1_B 重み付きunionfind
"""
def root(x):
    if par[x] == x:
        return x
    r = root(par[x])
    w[x] += w[par[x]]
    par[x] = r
    return par[x]

def same(x,y):
    return root(x) == root(y)

def unite(x,y,z):
    z += w[x]-w[y]
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
        w[x] = -z
    else:
        par[y] = x
        w[y] = z
        if rank[x] == rank[y]:
            rank[x] += 1
n,Q = LI()
par = [i for i in range(n)]
rank = [0 for i in range(n)]
w = [0 for i in range(n)]
for _ in range(Q):
    q = LI()
    if q[0]:
        x,y = q[1],q[2]
        if same(x,y):
            print(w[y]-w[x])
        else:
            print("?")
    else:
        x,y,z = q[1:]
        if not same(x,y):
            unite(x,y,z)
"""
#2:range quary
#2_A rmq
"""
def rmq(a,b,k,l,r):
    if r <= a or b <= l:
        return inf
    if a <= l and r <= b:
        return st[k]
    vl = rmq(a,b,2*k+1,l,(l+r)//2)
    vr = rmq(a,b,2*k+2,(l+r)//2,r)
    return min(vl,vr)

n,Q = LI()
n1 = 1
while n1 <= n:
    n1 *= 2
n = n1
inf = pow(2,31)-1
st = [inf for i in range(2*n-1)]
for _ in range(Q):
    q = LI()
    if not q[0]:
        x,y = q[1:]
        i = n+x-1
        st[i] = y
        while i > 0:
            i = (i-1)//2
            st[i] = min(st[2*i+1],st[2*i+2])
    else:
        a,b = q[1:]
        print(rmq(a,b+1,0,0,n))
"""

#2_B rsq
"""
def rsq(a,b,k,l,r):
    if r <= a or b <= l:
        return 0
        if a <= l and r <= b:
            return st[k]
            vl = rsq(a,b,2*k+1,l,(l+r)//2)
            vr = rsq(a,b,2*k+2,(l+r)//2,r)
            return vl+vr

            n,Q = LI()
            n1 = 1
            while n1 <= n:
                n1 *= 2
                n = n1
                st = [0 for i in range(2*n-1)]
                for _ in range(Q):
                    q = LI()
                    if not q[0]:
                        x,y = q[1:]
                        i = n+x-1
                        st[i] += y
                        while i > 0:
                            i = (i-1)//2
                            st[i] += y
                        else:
                            a,b = q[1:]
                            print(rsq(a,b+1,0,0,n))
"""
#2_C

#2_D
"""
def ruq(a,b,k,l,r,z):
    if r <= a or b <= l:
        return
    if a <= l and r <= b:
        st[k] = z
        return
    vl = ruq(a,b,2*k+1,l,(l+r)//2,z)
    vr = ruq(a,b,2*k+2,(l+r)//2,r,z)
    return

n,Q = LI()
n1 = 1
while n1 <= n:
    n1 *= 2
n = n1
d = pow(2,31)-1
st = [d for i in range(2*n-1)]
for _ in range(Q):
    q = LI()
    if not q[0]:
        x,y,z = q[1:]
        ruq(x,y+1,0,0,n,z)
    else:
"""
#2_E
def add(a,b,x,k = None,l = None,r = None):
    if k is None:
        k = 0
        l = 0
        r = n
    if a <= l and r <= b:
        data[k] += x
    elif l < b and a < r:
        datb[k] += (min(b, r)-max(a,l))*x
        add(a,b,x,k*2+1,l,(l+r)//2)
        add(a,b,x,k*2+2,(l+r)//2,r)

def get(a,b,k = None,l = None,r = None):
    if k is None:
        k = 0
        l = 0
        r = n
    if b <= l or r <= a:
        return 0
    elif a <= l and r <= b:
        return data[k]*(r-l)+datb[k]
    else:
        res = (min(b,r)-max(a,l))*data[k]
        res += get(a,b,k*2+1,l,(l+r)//2)
        res += get(a,b,k*2+2,(l+r)//2, r)
        return res

n,q = LI()
MAX_N = (1<<20)-1
data = [0]*MAX_N
datb = [0]*MAX_N
for i in range(q):
    query = LI()
    if query[0] == 0:
        s,t,x = query[1:]
        add(s-1,t,x)
    else:
        print(get(query[1]-1,query[1]))
#2_F

#2_G

#2_H

#2_I


#3:sliding window
#3_A
"""
n,s = MI()
a = LI()
for i in range(1,n):
    a[i] += a[i-1]
a.insert(0,0)
l = 0
r = 0
ans = float("inf")
if a[1] >= s:
    print(1)
    quit()
while r < n:
    r += 1
    if a[r]-a[l] >= s:
        while a[r]-a[l] >= s and l < r:
            l += 1
        ans = min(ans, r-l+1)
if ans == float("inf"):
    print(0)
    quit()
print(ans)
"""

#3_B
"""
n,k = MI()
a = LI()
l = 0
r = 0
ans = float("inf")
fl = [0 for i in range(k+1)]
s = 0
if k == 1 and a[0] == 1:
    print(1)
    quit()
if a[0] <= k:
    fl[a[0]] = 1
    s = 1
while r < n-1:
    r += 1
    if a[r] <= k:
        if not fl[a[r]]:
            s += 1
        fl[a[r]] += 1
    if s == k:
        while s == k:
            l += 1
            if a[l-1] <= k:
                if fl[a[l-1]] == 1:
                    s -= 1
                fl[a[l-1]] -= 1
        ans = min(ans, r-l+2)
if ans == float("inf"):
    print(0)
    quit()
print(ans)
"""

#3_C
"""
n,q = LI()
a = LI()
x = LI()
for i in range(q):
    ans = 0
    r = -1
    s = 0
    for l in range(n):
        while r+1 < n and s+a[r+1] <= x[i]:
            r += 1
            s += a[r]
        if s <= x[i]:
            ans += r-l+1
        if l == r:
            r += 1
            if r < n:
                s += a[r]
        s -= a[l]
    print(ans)
"""


#3_D
"""
n,l = LI()
a = LI()
k = [0 for i in range(l)]
for i in range(l):
    k[i] = a[i]
k.sort()
ans = [k[0]]
for i in range(n-l):
    j = bisect.bisect_left(k,a[i])
    x = k.pop(j)
    j = bisect.bisect_left(k,a[l+i])
    k.insert(j,a[l+i])
    ans.append(k[0])
for i in range(len(ans)-1):
    print(ans[i],end = " ")
print(ans[-1])
"""

#4:coordinate compression
#4_A
"""
n = int(sys.stdin.readline())
d = defaultdict(int)
lx = []
ly = []
for i in range(n):
    x,y,s,t = map(int,sys.stdin.readline()[:-1].split())
    d[(x,y)] += 1
    d[(x,t)] -= 1
    d[(s,y)] -= 1
    d[(s,t)] += 1
    i = bisect.bisect_left(lx,x)
    if i >= len(lx) or lx[i] != x:
        lx.insert(i,x)
    i = bisect.bisect_left(ly,y)
    if i >= len(ly) or ly[i] != y:
        ly.insert(i,y)
    i = bisect.bisect_left(lx,s)
    if i >= len(lx) or lx[i] != s:
        lx.insert(i,s)
    i = bisect.bisect_left(ly,t)
    if i >= len(ly) or ly[i] != t:
        ly.insert(i,t)

for x in lx:
    for j in range((len(ly))-1):
        d[(x,ly[j+1])] += d[(x,ly[j])]
for y in ly:
    for i in range((len(lx))-1):
        d[(lx[i+1],y)] += d[(lx[i],y)]
ans = 0
for j in range(len(ly)-1):
    y = ly[j]
    p_y = ly[j+1]
    for i in range(len(lx)-1):
        x = lx[i]
        p_x = lx[i+1]
        if d[(x,y)] >= 1:
            ans += (p_y-y)*(p_x-x)
print(ans)
"""
#5:comulative sum
#5_A
"""
n,t = map(int, input().split(" "))
num = [0 for i in range(t)]
for i in range(n):
    l,r = map(int, input().split(" "))
    num[l] += 1
    if r < t:
        num[r] -= 1
for i in range(1,t):
    num[i] += num[i-1]
print(max(num))
"""

#5_B
"""
n = int(input())
lec = [[0 for i in range(1001)] for j in range(1001)]
max_x = 0
max_y = 0
for i in range(n):
    x,y,s,t = map(int, input().split(" "))
    lec[y][x] += 1
    lec[y][s] -= 1
    lec[t][x] -= 1
    lec[t][s] += 1
    max_x = max(max_x, s)
    max_y = max(max_y, t)

for i in range(max_y+1):
    for j in range(1, max_x+1):
        lec[i][j] += lec[i][j-1]

for i in range(1, max_y+1):
    for j in range(max_x+1):
        lec[i][j] += lec[i-1][j]

ans = 0
for i in range(max_y+1):
    for j in range(max_x+1):
        ans = max(ans, lec[i][j])

print(ans)
"""

Submission status: Accepted

Solution code:
# AOJ DSL_2_E
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_E

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

def get(i, k, l, r):
    z = a[0]
    while True:
        m = (l + r) // 2
        if i < m:
            k = k * 2 + 1
            r = m
        else:
            k = k * 2 + 2
            l = m
        z += a[k]
        if k >= N - 1:
            break
    return z

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

for t in range(0, q):
    line = input()
    qu = list(map(int, line.split()))
    if qu[0] == 0:
        add(qu[1], qu[2]+1, qu[3], 0, 0, N)
    elif qu[0] == 1:
        ans = get(qu[1], 0, 0, N)
        print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
class Tree:
    def __init__(self, n):
        self.size = 2**((n-1).bit_length())
        self.a = [0]*(self.size*2)
        
    def find(self, c,l,r,i):
        if l == r:
            return self.a[c]
        mid = (l+r)//2
        if i <= mid:
            return self.a[c] + self.find(c*2,l,mid,i)
        else:
            return self.a[c] + self.find(c*2+1,mid+1,r,i)
    
    #この関数の考え方は勉強になる
    def add(self,c,l,r,s,t,x):
        if l == r or(l == s and t == r):
            self.a[c] += x
            return
        mid = (l+r)//2
        if t <= mid:
            self.add(c*2,l,mid,s,t,x)
        elif s > mid:
            self.add(c*2+1,mid+1,r,s,t,x)
        else:
            self.add(c*2,l,mid,s,mid,x)
            self.add(c*2+1,mid+1,r,mid+1,t,x)

n, q = map(int, input().split())
st = Tree(n)
for _ in range(q):
    cmt, *b = map(int, input().split())
    if cmt == 0:
        st.add(1,1,st.size,b[0],b[1],b[2])
    else:
        print(st.find(1,1,st.size,b[0]))

Submission status: Accepted

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


for i in range(30):#要素数以上の2のベキを見つける
    if n<1<<i:#前の問題と違って1-indexなので.
        seg_el=1<<i#Segment treeの台の要素数
        break

SEG=[0 for i in range(2*seg_el-1)]#Segment tree（遅延を用いるが、伝搬が不要。一本のセグ木でOK）

def update(a,b,x,k,l,r):  
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば終了
        return 
    if a<=l and r<=b:#区間[a,b)が対象区間の中にあればSEG[k]を更新.後にアクセスされたときに遅延評価する.
        SEG[k]+=x
        return 
    update(a,b,x,k*2+1,l,(l+r)//2)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け
    update(a,b,x,k*2+2,(l+r)//2,r)

def getvalue(n):#値を得る
    i=n+seg_el-1
    ANS=SEG[i]
    i=(i-1)//2
    height=1

    while i>=0:
        ANS+=SEG[i]#親をたどって得た和が答え
        i=(i-1)//2
        height+=1
    return ANS

for query in Q:
    if query[0]==0:
        update(query[1],query[2]+1,query[3],0,0,seg_el)
    else:
        print(getvalue(query[1]))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write
N, Q = map(int, readline().split())

data = [0]*(N+1)
def add(k, x):
    while k <= N:
        data[k] += x
        k += k & -k

def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s


ans = []
for q in range(Q):
    t, *cmd = map(int, readline().split())
    if t:
        ans.append(str(get(cmd[0])))
    else:
        s, t, x = cmd
        add(s, x)
        if t < N:
            add(t+1, -x)
write("\n".join(ans))
write("\n")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# DSL_2_E: Range Add Query


class SegmentTree:
    INITIAL_VALUE = 0

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

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

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

    def get(self, i):
        def _get(r, lo, hi, v):
            v += self.data[r]
            if lo == hi:
                return v
            mid = lo + (hi - lo)//2
            if mid >= i:
                return _get(r*2 + 1, lo, mid, v)
            else:
                return _get(r*2 + 2, mid+1, hi, v)

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


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

    for _ in range(q):
        com, *args = [i for i in input().split()]
        if com == '0':
            s, t, x = [int(i) for i in args]
            tree.add(s-1, t-1, x)

        elif com == '1':
            t = int(args[0])
            print(tree.get(t-1))
        else:
            raise ValueError('invalid command')


if __name__ == '__main__':
    run()