Problem:
RMQ and RAQ Write a program which manipulates a sequence $A$ = {$a_0, a_1, ..., a_{n-1}$} with the following operations:  $add(s, t, x)$ : add $x$ to $a_s, a_{s+1}, ..., a_t$.  $find(s, t)$ : report the minimum value in $a_s, a_{s+1}, ..., a_t$.  Note that the initial values of $a_i ( i = 0, 1, ..., n-1 )$ 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 $s$ $t$ The first digit represents the type of the query. '0' denotes $add(s, t, x)$  and '1' denotes $find(s, t)$. Output For each $find$ query, print the minimum value. Constraints  $1 ≤ n ≤ 100000$  $1 ≤ q ≤ 100000$  $0 ≤ s ≤ t < n$  $-1000 ≤ x ≤ 1000$  Sample Input 1 6 7
0 1 3 1
0 2 4 -2
1 0 5
1 0 1
0 3 5 3
1 3 4
1 0 5 Sample Output 1 -2
0
1
-1

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.length = self._build(lst) 
        self.lazy = [self.identity] * (2 * self.N)
    
    def __getitem__(self, i):
        return self.fold(i, i+1)
    
    def _build(self, lst):
        
        
        e, N, op = self.e, self.N, self.op
        tree = [e] * N + lst + [e] * (N - self.n)
        length = [1] * (2 * N)
        for i in range(N - 1, 0, -1):
            lc, rc = i << 1, (i << 1)|1
            tree[i] = op(tree[lc], tree[rc])
            length[i] = length[lc] + length[rc]
        return tree, length
    
    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, length, apply, comp = self.identity, self.v, self.lazy, self.length, self.apply, self.comp
        for k in reversed(indices):
            x = lazy[k]
            if x == identity: continue
            lc, rc = k << 1, (k << 1) | 1
            v[lc] = apply(v[lc], x, length[lc])
            lazy[lc] = comp(lazy[lc], x)
            v[rc] = apply(v[rc], x, length[rc])
            lazy[rc] = comp(lazy[rc], 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, length, apply, comp = self.N, self.v, self.lazy, self.length, self.apply, self.comp
        
        
        left = l + N; right = r + N
        if left & 1: v[left] = apply(v[left], x, length[left]); left += 1
        if right & 1: right -= 1; v[right] = apply(v[right], x, length[right])
        left >>= 1; right >>= 1
        while left < right:
            if left & 1:
                v[left] = apply(v[left], x, length[left])
                lazy[left] = comp(lazy[left], x)
                left += 1
            if right & 1:
                right -= 1
                v[right] = apply(v[right], x, length[right])
                lazy[right] = comp(lazy[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 = min
apply = lambda x, f, l: x + f
comp = lambda f, g: f + g
e = 2**31 - 1
identity = 0
A = [0] * 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, t+1, x)
    else:
        s, t = arg
        ans.append(lpsg.fold(s, t+1))
print('\n'.join(map(str, ans)))

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

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

seg_el=1<<(N.bit_length()) 
SEG=[0]*(2*seg_el) 
LAZY=[0]*(2*seg_el) 

def indexes(L,R): 
    INDLIST=[]

    R-=1
    
    L>>=1
    R>>=1

    while L!=R:
        if L>R:
            INDLIST.append(L)
            L>>=1
        else:
            INDLIST.append(R)
            R>>=1

    while L!=0:
        INDLIST.append(L)
        L>>=1

    return INDLIST
        

def adds(l,r,x): 
        
    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    while L!=R:
        if L > R:
            SEG[L]+=x
            LAZY[L]+=x
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            SEG[R]+=x
            LAZY[R]+=x
            R//=(R & (-R))

    for ind in UPIND:
        SEG[ind]=min(SEG[ind<<1],SEG[1+(ind<<1)])+LAZY[ind]
        
def getvalues(l,r): 

    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]: 
        if LAZY[ind]!=0:
            plus_lazy=LAZY[ind]
            
            SEG[ind<<1]+=plus_lazy
            SEG[1+(ind<<1)]+=plus_lazy
            
            LAZY[ind<<1]+=plus_lazy
            LAZY[1+(ind<<1)]+=plus_lazy
            
            LAZY[ind]=0
            
    ANS=1<<31

    while L!=R:
        if L > R:
            ANS=min(ANS , SEG[L])
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            ANS=min(ANS , SEG[R])
            R//=(R & (-R))

    return ANS

ANS=[]

for _ in range(Q):
    query=list(map(int,input().split()))
    if query[0]==0:
        adds(query[1],query[2]+1,query[3])

    else:
        ANS.append(getvalues(query[1],query[2]+1))

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

Solution (Python):


import sys

input = sys.stdin.readline
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 = 2 ** 31 - 1
MOD = 10 ** 9 + 7

class StarrySkyTree:
    """ Starry Sky Tree """

    def __init__(self, N, func, intv):
        self.intv = intv
        self.func = func
        LV = (N-1).bit_length()
        self.N0 = 2**LV
        self.data = [0]*(2*self.N0)
        self.lazy = [0]*(2*self.N0)

    
    def gindex(self, l, r):
        L = l + self.N0; R = r + self.N0
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1
        while L:
            yield L
            L >>= 1

    
    def propagates(self, *ids):
        
        for i in reversed(ids):
            v = self.lazy[i-1]
            if not v:
                continue
            self.lazy[2*i-1] += v; self.lazy[2*i] += v
            self.data[2*i-1] += v; self.data[2*i] += v
            self.lazy[i-1] = 0

    def update(self, l, r, x):
        """ 区間[l,r)の値にxを加算 """

        
        
        L = self.N0 + l; R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] += x; self.data[R-1] += x
            if L & 1:
                self.lazy[L-1] += x; self.data[L-1] += x
                L += 1
            L >>= 1; R >>= 1
        
        for i in self.gindex(l, r):
            self.data[i-1] = self.func(self.data[2*i-1], self.data[2*i]) + self.lazy[i-1]

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

        
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r

        
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.func(s, self.data[R-1])
            if L & 1:
                s = self.func(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

N, Q = MAP()
sst = StarrySkyTree(N+1, min, INF)

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

Solution (Python):
import sys
input = sys.stdin.readline
INF = 2**31 - 1

class StarrySkyTree:
    def __init__(self, n):
        LV = (n-1).bit_length()
        self.N0 = 2 ** LV
        self.data = [0] * (2*self.N0)
        self.lazy = [0] * (2*self.N0)
    
    def gindex(self, l, r):
        L = l + self.N0; R = r + self.N0
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        
        while L < R:
            if R <= rm:
                yield R
                
            if L <= lm:
                yield L
                
            L >>= 1; R >>= 1
            
        while L:
            yield L
            L >>= 1

    def propagates(self, *ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            
            if not v:
                continue
            
            self.lazy[2*i-1] += v; self.lazy[2*i] += v
            self.data[2*i-1] += v; self.data[2*i] += v
            self.lazy[i-1] = 0

    def update(self, l, r, x):
        L = self.N0 + l; R = self.N0 + r
        
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] += x; self.data[R-1] += x
                
            if L & 1:
                self.lazy[L-1] += x; self.data[L-1] += x
                L += 1
                
            L >>= 1; R >>= 1
            
        for i in self.gindex(l, r):
            self.data[i-1] = min(self.data[2*i-1], self.data[2*i]) + self.lazy[i-1]

    def query(self, l, r):
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r
        s = INF
        
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])
                
            if L & 1:
                s = min(s, self.data[L-1])
                L += 1
                
            L >>= 1; R >>= 1
            
        return s

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

for _ in range(q):
    que = list(map(int, input().split()))
    
    if que[0] == 0:
        s, t, x = que[1], que[2], que[3]
        sst.update(s, t+1, x)
    elif que[0] == 1:
        s, t = que[1], que[2]
        print(sst.query(s, t+1))

Solution (Python):
from array import array


class SegmentTree(object):
    MAXV = 1000 * 10**5 + 1

    def __init__(self, n: int) -> None:
        size = 1
        while (size < n):
            size *= 2
        self.size = 2 * size - 1
        self.data = array('i', [0] * self.size)
        self.lazy = array('i', [0] * self.size)

    def add(self, l: int, h: int, v: int) -> None:
        def _add(r, i: int, j: int, lz: int) -> int:
            left, right = r * 2 + 1, r * 2 + 2
            if lazy[r]:
                lz += lazy[r]
                lazy[r] = 0

            if (l <= i and j <= h):  
                lz += v
                if lz:
                    data[r] += lz
                    if (i < j):
                        lazy[left] += lz
                        lazy[right] += lz
            else:
                mid = (i + j) // 2
                if (mid >= l):
                    lv = _add(left, i, mid, lz)
                else:
                    lazy[left] += lz
                    lv = data[left] + lazy[left]

                if (mid < h):
                    rv = _add(right, mid + 1, j, lz)
                else:
                    lazy[right] += lz
                    rv = data[right] + lazy[right]

                if (lv < rv):
                    data[r] = lv
                else:
                    data[r] = rv

            return data[r]

        lazy = self.lazy
        data = self.data
        _add(0, 0, self.size // 2, 0)

    def min(self, l: int, h: int) -> int:
        def _min(r, i: int, j: int, lz: int) -> int:
            left, right = r * 2 + 1, r * 2 + 2
            if lazy[r]:
                lz += lazy[r]
                lazy[r] = 0
            if lz:
                data[r] += lz

            if (l <= i and j <= h):  
                if lz and i < j:
                    lazy[left] += lz
                    lazy[right] += lz
                return data[r]
            else:
                mid = (i + j) // 2
                if (mid >= l):
                    lv = _min(left, i, mid, lz)
                else:
                    lazy[left] += lz
                    lv = self.MAXV

                if (mid < h):
                    rv = _min(right, mid + 1, j, lz)
                else:
                    lazy[right] += lz
                    rv = self.MAXV

                if (lv < rv):
                    return lv
                else:
                    return rv

        lazy = self.lazy
        data = self.data
        return _min(0, 0, self.size // 2, 0)


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

    ans = []
    for _ in range(q):
        com, *v = map(lambda x: int(x), input().split())
        if (0 == com):
            segtree.add(v[0], v[1], v[2])
        else:
            ans.append(segtree.min(v[0], v[1]))

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

Solution (Python):
import sys
class Lazysegtree:
    
    def __init__(self, A, intv, initialize = True, segf = min):
        
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        self.lazy = [0]*(2*self.N0)
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)

    def _ascend(self, k):
        k = k >> 1
        c = k.bit_length()
        for j in range(c):
            idx = k >> j
            self.data[idx] = self.segf(self.data[2*idx], self.data[2*idx+1]) \
            + self.lazy[idx]
            
    def _descend(self, k):
        k = k >> 1
        idx = 1
        c = k.bit_length()
        for j in range(1, c+1):
            idx = k >> (c - j)
            ax = self.lazy[idx]
            if not ax:
                continue
            self.lazy[idx] = 0
            self.data[2*idx] += ax
            self.data[2*idx+1] += ax
            self.lazy[2*idx] += ax
            self.lazy[2*idx+1] += ax
    
    def query(self, l, r):
        L = l+self.N0
        R = r+self.N0
        Li = L//(L & -L)
        Ri = R//(R & -R)
        self._descend(Li)
        self._descend(Ri - 1)
        
        s = self.intv                                                              
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    
    def update(self, l, r, x):
        L = l+self.N0
        R = r+self.N0

        Li = L//(L & -L)
        Ri = R//(R & -R)
        
        while L < R :
            if R & 1:
                R -= 1
                self.data[R] += x
                self.lazy[R] += x
            if L & 1:
                self.data[L] += x
                self.lazy[L] += x
                L += 1
            L >>= 1
            R >>= 1
        
        self._ascend(Li)
        self._ascend(Ri-1)

N, Q = map(int, input().split())
T = Lazysegtree([0]*N, 2<<31) 
Ans = []
for jq in range(Q):
    t, *q = map(int, sys.stdin.readline().split())
    q[1] += 1
    if t:
        Ans.append(T.query(*q))
    else:
        T.update(*q)
print('\n'.join(map(str, Ans)))

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

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

Len = (n-1).bit_length()
size = 2**Len
tree = [0]*(2*size)
lazy = [0]*(2*size)
INF = 2**31 -1

def gindex(l,r):
    box = []
    L = (l+size)>>1;R=(r+size)>>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(Len):
        if rc <= i:
            box.append(R)
        if L < R and lc <= i:
            box.append(L)
        L >>= 1; R >>= 1
    return box
        
        

def propagates(ids):
    for i in reversed(ids):
        v = lazy[i]
        if v is None:
            continue
        lazy[2*i] += v
        tree[2*i] += v
        lazy[2*i+1] += v
        tree[2*i+1] += v
        lazy[i]=0

def update(l,r,x):
    L = size+l
    R = size+r
    while L<R:
        if R&1:
            R -= 1
            lazy[R] += x
            tree[R] += x
        if L&1:
            lazy[L] += x
            tree[L] += x
            L+=1
        L>>=1;R>>=1
    ids = gindex(l,r)
    for i in ids:
        if 2*i+1<size*2:
            tree[i]= min(tree[i*2],tree[i*2+1]) + lazy[i]
        
def query(l, r):
    ids = gindex(l, r)
    propagates(ids)
    L = size + l
    R = size + r
    s = INF
    while L<R:
        if R&1:
            R-=1
            s =min(s, tree[R])
        if L&1:
            s =min(s, tree[L])
            L+=1
        L>>=1;R>>=1
    return s

ans = []
for i in range(q):
    a, *b = map(int, input().split())
    if a:
        ans.append(query(b[0],b[1]+1))
    else:
        update(b[0],b[1]+1,b[2])
        
print('\n'.join(map(str,ans)))