Problem:
Range Add Query (RAQ) Write a program which manipulates a sequence A = { a 1 , a 2 , . . .  , a n } with the following operations:  add(s, t, x) : add x to a s , a s+1 , ..., a t .  get(i) : output the value of a i .  Note that the initial values of a i ( i = 1, 2, . . .  , n ) are 0. Input  n  q  query 1  query 2 : query q  In the first line, n (the number of elements in A ) and q (the number of queries) are given. Then, i th query query i 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

Solution (Python):
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
    return self.value[x]

  def update(self, x, add, left, right):
    x_left, x_right = self.range[x]
    if right < x_left or x_right < left:
      pass
    elif left <= x_left and x_right <= right:
      self.value[x] += add
    else:
      self.update(x * 2 + 1, add, left, right)
      self.update(x * 2 + 2, add, left, right)
  
  def query(self, x, total):
    if x < 0:return total
    total += self.value[x]
    return self.query((x - 1) // 2, total)

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

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

for _ in range(q):
  lst = list(map(int, input().split()))
  if lst[0] == 0:
    s, t, x = lst[1:]
    tree.update(0, x, s - 1, t - 1)
  else:
    i = lst[1]
    print(tree.query(tree.iter_size - 1 + i - 1, 0))

Solution (Python):
N, Q =map(int, input().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):
  a = input()
  if a[0] == "1":
    ans.append(str(get(int(a[2:]))))
  else:
    s, t, x = map(int, a[2:].split())
    add(s, x)
    if t < N:
      add(t+1, -x)
for i in ans:
  print(i)

Solution (Python):
N,Q = map(int, input().split())

data = [0]*(N+1)
def add(k, x,y):
    while k <= N:
        data[k] += y
        k += k & -k
    x+=1
    while x <= N:
        data[x] -= y
        x += x & -x
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
for i in range(Q):
    t = list(map(int, input().split()))
    if t[0] == 1:
        print(get(t[1]))
    else:
        add(t[1],t[2],t[3])

Solution (Python):
from math import log2, ceil


class SegmentTree:
    def __init__(self, n):
        tn = 2 ** ceil(log2(n))
        self.a = [0] * (tn * 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 r == t:
            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 = SegmentTree(n)
for _ in range(q):
    query = input().split()
    if query[0] == '0':
        
        s, t, x = map(int, query[1:])
        st.add(1, 1, n, s, t, x)
    else:
        print(st.find(1, 1, n, int(query[1])))

Solution (Python):
import sys

def solve():
    n, q = map(int, sys.stdin.readline().split())

    ft = FenwickTree(n)

    for qi in range(q):
        query = sys.stdin.readline().rstrip()

        if query[0] == '0':
            c, s, t, x = map(int, query.split())
            ft.add(s, x)
            ft.add(t + 1, -x)
        else:
            c, i = map(int, query.split())

            print(ft.get_sum(i))


class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.data = [0]*(size + 1)

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

    def get_sum(self, r):
        res = 0

        while r > 0:
            res += self.data[r]
            r -= r & (-r)

        return res

if __name__ == '__main__':
    solve()

Solution (Python):
import math


def hoge(s, e, value):
    s += l
    e += l
    d, l_running, r_running = rank, 1, 1

    while l_running or r_running:
        l_end_node, r_end_node = s >> d, e >> d
        l_end_leaf = l_end_node << d, (l_end_node + 1 << d) - 1
        r_end_leaf = r_end_node << d, (r_end_node + 1 << d) - 1

        if l_end_node == r_end_node:
            if l_end_leaf[0] == s and r_end_leaf[1] == e:
                
                lazy[l_end_node] += value
                break
        else:
            if l_running:
                if l_end_leaf[0] == s:
                    
                    lazy[l_end_node] += value
                    l_running = 0
                
                elif l_end_node >> 1 << 1 == l_end_node and l_end_node+1 < r_end_node:
                    
                    lazy[l_end_node+1] += value

            if r_running:
                if r_end_leaf[1] == e:
                    
                    lazy[r_end_node] += value
                    r_running = 0
                elif r_end_node >> 1 << 1 == r_end_node-1 and l_end_node+1 < r_end_node:
                    
                    lazy[r_end_node-1] += value

        if d > 0:
            
            if l_running:
                lazy_left, lazy[l_end_node] = lazy[l_end_node], 0
                lazy[l_end_node << 1] += lazy_left
                lazy[(l_end_node << 1)+1] += lazy_left
            if r_running:
                lazy_right, lazy[r_end_node] = lazy[r_end_node], 0
                lazy[r_end_node << 1] += lazy_right
                lazy[(r_end_node << 1)+1] += lazy_right

        d -= 1

def get_value(i):
    i += l
    v = 0
    for j in range(rank, -1, -1):
        v += lazy[i>>j]
    return v + tree[i]

n, q = map(int,input().split())
l = 1 << math.ceil(math.log2(n))
tree = [0]*(2*l)
lazy = [0]*(2*l)
rank = int(math.log2(len(tree)))
ans = []
ap = ans.append

for _ in [None]*q:
    query = list(map(int, input().split()))
    if query[0] == 0:
        hoge(query[1]-1, query[2]-1, query[3])
    else:
        ap(get_value(query[1]-1))

print("\n".join((str(n) for n in ans)))

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

def solve():
  ans = []
  N, Q = map(int, input().split())
  data0 = BIT(N+1)
  data1 = BIT(N+1)
  for i in range(Q):
    p,*y = map(int, input().split())
    if p==0:
      l,r,x = y
      data0.add(l,-x*(l-1))
      data0.add(r+1,x*r)
      data1.add(l,x)
      data1.add(r+1,-x)
    else:
      r = y[0]
      ans.append(data1.sum(r)*r+data0.sum(r)-data1.sum(r-1)*(r-1)-data0.sum(r-1))
  return ans
print(*solve(),sep='\n')

Solution (Python):
class fenwick_tree:
    """
    区間の一点更新と，区間和の取得がO(log n)で可能なデータ構造
    1-indexedで実装
    """

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

    def init_array(self, A):
        for i, a in enumerate(A, start=1):
            self.add(i, a)

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

    def sum_acc(self, i, j):
        """ [i,j] の和を返す """
        return self.sum_until(j) - self.sum_until(i-1)

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


class fenwick_tree_interval_add(fenwick_tree):
    """
    区間加算と，一点取得がO(log n)
    区間和を求めるのは，区間の長さをkとして，O(k)
    """

    def __init__(self, n):
        super().__init__(n)

    def init_array(self, A):
        for i in range(self.size):
            if i != 0:
                self.__add(i+1, A[i] - A[i-1])
            else:
                self.__add(i+1, A[i])

    def add_interval(self, i, j, w):
        if i <= 0 or self.size < j or j < i:
            raise IndexError
        self.__add(i, w)
        if j < self.size:
            self.__add(j+1, -w)

    def get_val(self, i):
        if i <= 0 or self.size < i:
            raise IndexError
        return self.__sum_until(i)

    def __sum_until(self, i):
        return super().sum_until(i)

    def __add(self, i, x):
        super().add(i, x)


def main():
    N, Q = (int(i) for i in input().split())
    bit = fenwick_tree_interval_add(N)
    for _ in range(Q):
        com, *A = (int(i) for i in input().split())
        if com == 0:
            (x, y, w) = A
            bit.add_interval(x, y, w)
        else:
            x = A[0]
            print(bit.get_val(x))


if __name__ == '__main__':
    main()

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 range_update(table, left, right, action):
    left += SEGTREE_SIZE // 2
    right += SEGTREE_SIZE // 2
    while left < right:
        if left & 1:
            table[left] = action(table[left])
            left += 1
        if right & 1:
            right -= 1
            table[right] = action(table[right])
        left //= 2
        right //= 2


def down_propagate_to_leaf(table, pos, binop, unity):
    pos += NONLEAF_SIZE
    down_propagate(table, pos, binop, unity)
    return table[pos]


def down_propagate(table, pos, binop, unity):
    for max_level in range(N):
        if 2 ** max_level > pos:
            max_level -= 1
            break
    for level in range(max_level):
        i = pos >> (max_level - level)

        table[i * 2] = binop(table[i], table[i * 2])
        table[i * 2 + 1] = binop(table[i], table[i * 2 + 1])
        table[i] = unity


def set_items(table, xs):
    for i, x in enumerate(xs, NONLEAF_SIZE):
        table[i] = x


def debugprint(xs, minsize=0, maxsize=None):
    strs = [str(x) for x in xs]
    if maxsize != None:
        for i in range(NONLEAF_SIZE, SEGTREE_SIZE):
            strs[i] = strs[i][:maxsize]
    s = max(len(s) for s in strs[NONLEAF_SIZE:])
    if s > minsize:
        minsize = s

    result = ["|"] * N
    level = 0
    next_level = 2
    for i in range(1, SEGTREE_SIZE):
        if i == next_level:
            level += 1
            next_level *= 2
        width = ((minsize + 1) << (N - 1 - level)) - 1
        result[level] += strs[i].center(width) + "|"
    print(*result, sep="\n")


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 time in range(Q):
        q, *args = map(int, input().split())
        if q == 0:
            
            s, t, value = args
            range_update(table, s, t + 1, lambda x: x + value)

        else:
            
            print(down_propagate_to_leaf(
                table, args[0], add, 0))



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


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    3
    5
    """



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

import sys
input = sys.stdin.readline

class Bit:
    def __init__(self, n):
        self.n = n
        self.tree = [0]*(n+1)
        self.el = [0]*(n+1)
        self.depth = n.bit_length()

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1) )- 1
        return s

    def add(self, i, x):
        self.el[i] += x
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

    def get(self, i, j=None):
        """ 部分区間和 [i, j) """
        if j is None:
            return self.el[i]
        if i == 0:
            return self.sum(j)
        return self.sum(j) - self.sum(i)

    def lower_bound(self, x, equal=False):
        """ (a0+a1+...+ai < x となる最大の i, その時の a0+a1+...+ai )
             a0+a1+...+ai <= x としたい場合は equal = True         """
        sum_ = 0
        pos = -1    
        if not equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k <= self.n and sum_ + self.tree[k] < x:
                    sum_ += self.tree[k]
                    pos += 1 << i
        if equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k <= self.n and sum_ + self.tree[k] <= x:
                    sum_ += self.tree[k]
                    pos += 1 << i
        return pos, sum_

    def __getitem__(self, s):
        """ [a0, a1, a2, ...] """
        return self.el[s]

    def __iter__(self):
        """ [a0, a1, a2, ...] """
        for s in self.el[:self.n]:
            yield s

    def __str__(self):
        text1 = " ".join(["element: "] + list(map(str, self)))
        text2 = " ".join(["cumsum:  "] + list(str(self.sum(i)) for i in range(1, self.n + 1)))
        return "\n".join((text1, text2))


class BitImos:
    def __init__(self, n):
        self.n = n
        self.p = Bit(self.n + 1)
        self.q = Bit(self.n + 1)

    def add(self, s, t, x):
        """ 区間は閉区間 [s,t] で与えられる。原理は Imos法 と同じ。"""
        t += 1
        self.p.add(s, -x * s)
        self.p.add(t, x * t)
        self.q.add(s, x)
        self.q.add(t, -x)

    def sum(self, s, t):
        """ 半閉区間[s,t)の累積和を与える """
        return self.p.sum(t) + self.q.sum(t) * t - self.p.sum(s) - self.q.sum(s) * s

    def __getitem__(self, s):
        """ 区間加算後の s 番目の要素をO(log N)で取り出す。Imos法だとこの操作にO(N)かかる。"""
        return self.q.sum(s+1)

    def __iter__(self):
        """ max(self) で普段 Imos法 でやってることが出来る。"""
        for t in range(self.n):
            yield self.q.sum(t+1)

    def __str__(self):
        text1 = " ".join(["element: "] + list(map(str, self)))
        return text1

N, Q = map(int, input().split())
BI = BitImos(N)

for _ in range(Q):
    q = list(map(int, input().split()))
    if q[0] == 0:
        BI.add(q[1]-1,q[2]-1,q[3])
    else:
        print(BI[q[1]-1])

Solution (Python):
class LazySegTree:
    INF = 0
    def __init__(self,n_):
        self.n_ = n_
        self.n = 1
        while self.n < n_: self.n*=2
        self.lazy = [self.INF]*(2*self.n-1)

    def update(self,a,b,k,x,l,r):
        if r<=a or b<=l :return
        if a<=l and r<=b:
            self.lazy[k] += x
            return
        self.update(a,b,k*2+1,x,l,(l+r)//2)
        self.update(a,b,k*2+2,x,(l+r)//2,r)

    def Update(self,a,b,x):
        return self.update(a,b,0,x,0,self.n)

    def search(self,k,l,r):
        k += self.n-1
        res = self.INF
        while 0<=k:
            res += self.lazy[k]
            k = (k-1)//2
        return res

    def Search(self,k):
        return self.search(k,0,self.n)

def main():
    n,m = map(int,input().split())
    lst = LazySegTree(n)
    for _ in range(m):
        q = list(map(int,input().split()))
        if q[0] == 0:
            lst.Update(q[1]-1,q[2],q[3])
        else        :
            print(lst.Search(q[1]-1))

if __name__ == '__main__':
    main()

Solution (Python):

"""
Range Add Query (RAQ)
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_E&lang=ja

"""
import sys


def main(args):
    def add(b, k, x):
        while k <= n:
            b[k] += x
            k += k & -k

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

    n, queries = map(int, input().split())
    bit0 = [0] * (n + 1)
    bit1 = [0] * (n + 1)

    for _ in range(queries):
        q, *args = input().split()
        args = [int(a) for a in args]
        if q == '1':
            res = get(bit0, args[0]) + get(bit1, args[0]) * args[0]
            res -= get(bit0, args[0] - 1) + get(bit1, args[0] - 1) * (args[0] - 1)
            print(res)
        else:
            add(bit0, args[0], -args[2] * (args[0] - 1))
            add(bit1, args[0], args[2])
            add(bit0, args[1] + 1, args[2]* args[1])
            add(bit1, args[1] + 1, -args[2])


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
class SegmentTree:
    seg_len = 1
    node = []
    def __init__(self, n):
        while self.seg_len < n:
            self.seg_len <<= 1
        self.node = [ 0 for _ in range(self.seg_len*2) ]

    def add(self, l, r, x):
        l += self.seg_len
        r += self.seg_len
        while l < r:
            if l & 1 == 1:
                self.node[l] += x
                l += 1
            if r & 1 == 1:
                self.node[r-1] += x
                r -= 1
            l >>= 1; r >>= 1;

    def get(self, idx):
        idx += self.seg_len
        ret = self.node[idx]
        while True:
            idx >>= 1
            if idx == 0:
                break
            ret += self.node[idx]
        return ret

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

for _ in range(q):
    query = [ int(x) for x in input().split() ]
    if len(query) == 4:
        _, l, r, x = query
        l -= 1; r -= 1
        seg_tree.add(l, r+1, x)
    if len(query) == 2:
        _, i = query
        i -= 1;
        print(seg_tree.get(i))

Solution (Python):
import sys
input = sys.stdin.readline

class LazyPropSegmentTree:
    def __init__(self, lst, op, apply, comp, e, identity):
        self.n = len(lst)
        self.depth = (self.n - 1).bit_length()
        self.N = 1 << self.depth
        self.op = op 
        self.apply = apply 
        self.comp = comp 
        self.e = e 
        self.identity = identity 
        self.v = self._build(lst) 
        self.lazy = [self.identity] * (2 * self.N)
    
    def __getitem__(self, i):
        return self.fold(i, i+1)
    
    def _build(self, lst):
        
        
        tree = [self.e] * (self.N) + lst + [self.e] * (self.N - self.n)
        for i in range(self.N - 1, 0, -1): tree[i] = self.op(tree[i << 1], tree[(i << 1)|1])
        return tree
    
    def _indices(self, l, r):
        left = l + self.N; right = r + self.N
        left //= (left & (-left)); right //= (right & (-right))
        left >>= 1; right >>= 1
        while left != right:
            if left > right: yield left; left >>= 1
            else: yield right; right >>= 1
        while left > 0: yield left; left >>= 1
    
    
    def _propagate_topdown(self, *indices):
        identity, v, lazy, apply, comp = self.identity, self.v, self.lazy, self.apply, self.comp
        for k in reversed(indices):
            x = lazy[k]
            if x == identity: continue
            lazy[k << 1] = comp(lazy[k << 1], x)
            lazy[(k << 1)|1] = comp(lazy[(k << 1)|1], x)
            v[k << 1] = apply(v[k << 1], x)
            v[(k << 1)|1] = apply(v[(k << 1)|1], x)
            lazy[k] = identity 

    
    def _propagate_bottomup(self, indices):
        v, op = self.v, self.op
        for k in indices: v[k] = op(v[k << 1], v[(k << 1)|1])

    
    def update(self, l, r, x):
        *indices, = self._indices(l, r)
        self._propagate_topdown(*indices)
        
        N, v, lazy, apply, comp = self.N, self.v, self.lazy, self.apply, self.comp
        
        
        left = l + N; right = r + N
        if left & 1: v[left] = apply(v[left], x); left += 1
        if right & 1: right -= 1; v[right] = apply(v[right], x)
        left >>= 1; right >>= 1
        while left < right:
            if left & 1:
                lazy[left] = comp(lazy[left], x)
                v[left] = apply(v[left], x)
                left += 1
            if right & 1:
                right -= 1
                lazy[right] = comp(lazy[right], x)
                v[right] = apply(v[right], x)
            left >>= 1; right >>= 1
        self._propagate_bottomup(indices)
    
    
    def fold(self, l, r):
        self._propagate_topdown(*self._indices(l, r))
        
        e, N, v, op = self.e, self.N, self.v, self.op
        
        
        left = l + N; right = r + N
        L = R = e
        while left < right:
            if left & 1: 
                L = op(L, v[left])
                left += 1
            if right & 1: 
                right -= 1
                R = op(v[right], R)
            left >>= 1; right >>= 1
        return op(L, R)

N, Q = map(int, input().split())
op = lambda x, y: x+y
apply = lambda x, f: x+f
comp = lambda f, g: f+g
e = 0
identity = 0
A = [e] * N
lpsg = LazyPropSegmentTree(A, op, apply, comp, e, identity)
ans = []
for _ in range(Q):
    t, *arg, = map(int, input().split())
    if t == 0:
        s, t, x = arg
        lpsg.update(s-1, t, x)
    else:
        ans.append(lpsg[arg[0]-1])
print('\n'.join(map(str, ans)))

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

Solution (Python):

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

    
    def update(self,l,r,x):
        
        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])

    
    def query(self,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


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

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

Solution (Python):


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

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