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





from array import array
import sys


class SegmentTree:
    MAXV = 1000 * 10**5 + 1

    def __init__(self, n):
        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, lo, hi, v):
        def _add(r, i, j, lz):
            left, right = r*2 + 1, r*2 + 2
            if lazy[r]:
                lz += lazy[r]
                lazy[r] = 0

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

                if mid < hi:
                    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, lo, hi):
        def _min(r, i, j, lz):
            left, right = r*2 + 1, r*2 + 2
            if lazy[r]:
                lz += lazy[r]
                lazy[r] = 0
            if lz:
                data[r] += lz

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

                if mid < hi:
                    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)


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

    tree = SegmentTree(n)

    ret = []
    for line in sys.stdin:
        com, *args = line.split()
        if com == '0':
            s, t, x = map(int, args)
            tree.add(s, t, x)
        elif com == '1':
            s, t = map(int, args)
            ret.append(tree.min(s, t))

    sys.stdout.write("\n".join([str(i) for i in ret]))
    sys.stdout.write("\n")


if __name__ == '__main__':
    run()

Solution (Python):
import sys
readline = sys.stdin.readline
write = sys.stdout.write

N, Q = map(int, input().split())
INF = 2**31-1

LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [0]*(2*N0)

def gindex(l, r):
    L = l + N0; R = r + 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(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if not v:
            continue
        lazy[2*i-1] += v; lazy[2*i] += v
        data[2*i-1] += v; data[2*i] += v
        lazy[i-1] = 0

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

def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s


ans = []
for q in range(Q):
    t, *cmd = map(int, readline().split())
    if t:
        s, t = cmd
        ans.append(str(query(s, t+1)))
    else:
        s, t, x = cmd
        update(s, t+1, x)

write("\n".join(ans))
write("\n")

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


class RangeAddMin():
    def __init__(self, n):
        i = 1
        while 2**i <= n:
            i += 1
        self.N = 2**i
        self.A = [0] * (self.N*2)
        self.B = [0] * (self.N*2)

    def add(self, a, b, x, k, l, r):
        def ina(k, l, r):
            if b <= l or r <= a:
                pass
            elif a <= l and r <= b:
                self.A[k] += x
            else:
                m = (l+r) // 2
                ina(k*2+1, l, m)
                ina(k*2+2, m, r)
                self.B[k] = min(self.B[k*2+1] + self.A[k*2+1], self.B[k*2+2] + self.A[k*2+2])

        ina(k, l, r)

    def query(self, a, b, k, l, r):
        def inq(k, l, r):
            if b <= l or r <= a:
                return inf

            if a <= l and r <= b:
                return self.A[k] + self.B[k]

            m = (l+r) // 2
            rl = inq(k*2+1, l, m)
            rr = inq(k*2+2, m, r)
            return min(rl, rr) + self.A[k]

        return inq(k, l, r)

def main():
    n,q = LI()
    qa = [LI() for _ in range(q)]

    ram = RangeAddMin(n)
    rr = []
    for qi in qa:
        s = qi[1]
        t = qi[2] + 1
        if qi[0] == 0:
            x = qi[3]
            ram.add(s, t, x, 0, 0, n)
        else:
            rr.append(ram.query(s, t, 0, 0, n))

        

    return JA(rr, "\n")


print(main())

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def set_depth(depth):
    global DEPTH, SEGTREE_SIZE, NONLEAF_SIZE
    DEPTH = depth
    SEGTREE_SIZE = 1 << DEPTH
    NONLEAF_SIZE = 1 << (DEPTH - 1)


def set_width(width):
    set_depth((width - 1).bit_length() + 1)


def get_size(pos):
    ret = pos.bit_length()
    return (1 << (DEPTH - ret))


def up(pos):
    pos += SEGTREE_SIZE // 2
    return pos // (pos & -pos)


def up_propagate(table, pos, binop):
    while pos > 1:
        pos >>= 1
        table[pos] = binop(
            table[pos * 2],
            table[pos * 2 + 1]
        )


def force_down_propagate(
    action_table, value_table, pos,
    action_composite, action_force, action_unity
):
    max_level = pos.bit_length() - 1
    size = NONLEAF_SIZE
    for level in range(max_level):
        size //= 2
        i = pos >> (max_level - level)
        action = action_table[i]
        if action != action_unity:
            
            
            
            
            action_table[i * 2] += action
            action_table[i * 2 + 1] += action
            action_table[i] = action_unity
            
            
            
            
            value_table[i * 2] += action
            value_table[i * 2 + 1] += action


def force_range_update(
    value_table, action_table, left, right,
    action, action_force, action_composite, action_unity
):
    """
    action_force: action, value, cell_size => new_value
    action_composite: new_action, old_action => composite_action
    """
    left += NONLEAF_SIZE
    right += NONLEAF_SIZE
    while left < right:
        if left & 1:
            value_table[left] = action_force(
                action, value_table[left], get_size(left))
            action_table[left] = action_composite(action, action_table[left])
            left += 1
        if right & 1:
            right -= 1
            value_table[right] = action_force(
                action, value_table[right], get_size(right))
            action_table[right] = action_composite(action, action_table[right])

        left //= 2
        right //= 2


def range_reduce(table, left, right, binop, unity):
    ret_left = unity
    ret_right = unity
    left += NONLEAF_SIZE
    right += NONLEAF_SIZE
    while left < right:
        if left & 1:
            ret_left = binop(ret_left, table[left])
            left += 1
        if right & 1:
            right -= 1
            ret_right = binop(table[right], ret_right)

        left //= 2
        right //= 2
    return binop(ret_left, ret_right)


def lazy_range_update(
        action_table, value_table, start, end,
        action, action_composite, action_force, action_unity, value_binop):
    "update [start, end)"
    L = up(start)
    R = up(end)
    force_down_propagate(
        action_table, value_table, L,
        action_composite, action_force, action_unity)
    force_down_propagate(
        action_table, value_table, R,
        action_composite, action_force, action_unity)

    
    
    
    
    

    force_range_update(
        value_table, action_table, start, end,
        action, action_force, action_composite, action_unity)
    up_propagate(value_table, L, value_binop)
    up_propagate(value_table, R, value_binop)


def lazy_range_reduce(
    action_table, value_table, start, end,
    action_composite, action_force, action_unity,
    value_binop, value_unity
):
    "reduce [start, end)"
    force_down_propagate(
        action_table, value_table, up(start),
        action_composite, action_force,  action_unity)
    force_down_propagate(
        action_table, value_table, up(end),
        action_composite, action_force, action_unity)

    return range_reduce(value_table, start, end, value_binop, value_unity)


def debugprint(xs, minsize=0, maxsize=None):
    global DEPTH
    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 = ["|"] * DEPTH
    level = 0
    next_level = 2
    for i in range(1, SEGTREE_SIZE):
        if i == next_level:
            level += 1
            next_level *= 2
        width = ((minsize + 1) << (DEPTH - 1 - level)) - 1
        result[level] += strs[i].center(width) + "|"
    print(*result, sep="\n", file=sys.stderr)


def full_up(table, binop):
    for i in range(NONLEAF_SIZE - 1, 0, -1):
        table[i] = binop(
            table[2 * i],
            table[2 * i + 1])


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


def main():
    
    N, Q = map(int, input().split())
    set_width(N)

    value_unity = 10 ** 9
    value_table = [0] * SEGTREE_SIZE
    set_items(value_table, [0] * N)
    full_up(value_table, min)
    value_binop = min
    action_unity = 0
    action_table = [action_unity] * SEGTREE_SIZE

    def force(action, value, size):
        return action + value

    def composite(new_action, old_action):
        return new_action + old_action

    for time in range(Q):
        q, *args = map(int, input().split())
        if q == 0:
            
            s, t, value = args
            lazy_range_update(
                action_table, value_table, s, t + 1,
                value, composite, force, action_unity, value_binop)

        else:
            
            s, t = args
            print(lazy_range_reduce(
                action_table, value_table, s, t + 1,
                composite, force, action_unity, value_binop, value_unity))
        
        



T1 = """
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
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
-2
0
1
-1
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g)


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


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Solution (Python):

def segfunc(x, y):
    return min(x, y)



ide_ele = 2**31 - 1


class LazySegmentTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    add(l, r, x): 区間[l, r)にxを加算 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        num: n以上の最小の2のべき乗
        data: 値配列(1-index)
        lazy: 遅延配列(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.data = [ide_ele] * 2 * self.num
        self.lazy = [0] * 2 * self.num
        
        for i in range(n):
            self.data[self.num + i] = init_val[i]
        
        for i in range(self.num - 1, 0, -1):
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])

    def gindex(self, l, r):
            """
            伝搬する対象の区間を求める
            lm: 伝搬する必要のある最大の左閉区間
            rm: 伝搬する必要のある最大の右開区間
            """
            l += self.num
            r += self.num
            lm = l >> (l & -l).bit_length()
            rm = r >> (r & -r).bit_length()

            while r > l:
                if l <= lm:
                    yield l
                if r <= rm:
                    yield r
                r >>= 1
                l >>= 1
            while l:
                yield l
                l >>= 1

    def propagates(self, *ids):
        """
        遅延伝搬処理
        ids: 伝搬する対象の区間 
        """
        for i in reversed(ids):
            v = self.lazy[i]
            if not v:
                continue
            self.lazy[2 * i] += v
            self.lazy[2 * i + 1] += v
            self.data[2 * i] += v
            self.data[2 * i + 1] += v
            self.lazy[i] = 0

    def add(self, l, r, x):
        """
        区間[l, r)の値にxを加算
        l, r: index(0-index)
        x: additional value
        """
        *ids, = self.gindex(l, r)
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                self.lazy[l] += x
                self.data[l] += x
                l += 1
            if r & 1:
                self.lazy[r - 1] += x
                self.data[r - 1] += x
            r >>= 1
            l >>= 1
        for i in ids:
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1]) + self.lazy[i]


    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        *ids, = self.gindex(l, r)
        self.propagates(*ids)

        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.data[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.data[r - 1])
            l >>= 1
            r >>= 1
        return res
n, q = [int(x) for x in input().split()]
seg = LazySegmentTree([0]*n, segfunc, ide_ele)
for _ in range(q):
    a, *b = [int(x) for x in input().split()]
    if not a:
        s, t, x = b
        seg.add(s, t + 1, x)
    else:
        s, t = b
        print(seg.query(s, t + 1))

Solution (Python):
import sys,queue,math,copy,itertools,bisect
sys.setrecursionlimit(10**7)
INF = 10**10
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N,Q = LI()
N0 = 2 ** (N.bit_length())
node = [0 for _ in range(N0*2)]
lazy = [0 for _ in range(N0*2)]


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

def eval(*ids):
    for i in reversed(ids):
        v = lazy[i]
        if v:
            lazy[i*2+1] += v
            lazy[i*2+2] += v
            node[i*2+1] += v
            node[i*2+2] += v
        lazy[i] = 0

def data_add(l,r,v):
    *ids, = gindex(l,r)
    eval(*ids)

    L = l + N0; R = r + N0
    while L < R:
        if R % 2:
            R -= 1
            lazy[R-1] += v
            node[R-1] += v
        if L % 2:
            lazy[L-1] += v
            node[L-1] += v
            L += 1
        L //= 2; R //= 2

    for i in ids:
        node[i] = min(node[i*2+1],node[i*2+2])

def data_get(l,r):
    eval(*gindex(l,r))

    ret = INF
    L = l + N0; R = r + N0
    while L < R:
        if R % 2:
            R -= 1
            ret = min(ret,node[R-1])
        if L % 2:
            ret = min(ret,node[L-1])
            L += 1
        L //= 2; R //= 2
    return ret

for _ in range(Q):
    s = LI()
    if s[0] == 0:
        data_add(s[1],s[2]+1,s[3])
    else:
        print (data_get(s[1],s[2]+1))

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

    class LazySegTree:
        
        def __init__(self, A, initialize=True, segfunc=min, ident=2000000000):
            self.N = len(A)
            self.LV = (self.N - 1).bit_length()
            self.N0 = 1 << self.LV
            self.segfunc = segfunc
            self.ident = ident
            if initialize:
                self.data = [self.ident] * self.N0 + A + [self.ident] * (self.N0 - self.N)
                for i in range(self.N0 - 1, 0, -1):
                    self.data[i] = segfunc(self.data[i * 2], self.data[i * 2 + 1])
            else:
                self.data = [self.ident] * (self.N0 * 2)
            self.lazy = [0] * (self.N0 * 2)

        def _ascend(self, i):
            for _ in range(i.bit_length() - 1):
                i >>= 1
                self.data[i] = self.segfunc(self.data[i * 2], self.data[i * 2 + 1]) + self.lazy[i]

        def _descend(self, idx):
            lv = idx.bit_length()
            for j in range(lv - 1, 0, -1):
                i = idx >> j
                x = self.lazy[i]
                if not x:
                    continue
                self.lazy[i] = 0
                self.lazy[i * 2] += x
                self.lazy[i * 2 + 1] += x
                self.data[i * 2] += x
                self.data[i * 2 + 1] += x

        
        def add(self, l, r, x):
            l += self.N0 - 1
            r += self.N0 - 1
            l_ori = l
            r_ori = r
            while l < r:
                if l & 1:
                    self.data[l] += x
                    self.lazy[l] += x
                    l += 1
                if r & 1:
                    r -= 1
                    self.data[r] += x
                    self.lazy[r] += x
                l >>= 1
                r >>= 1
            self._ascend(l_ori // (l_ori & -l_ori))
            self._ascend(r_ori // (r_ori & -r_ori) - 1)

        
        def query(self, l, r):
            l += self.N0 - 1
            r += self.N0 - 1
            self._descend(l // (l & -l))
            self._descend(r // (r & -r) - 1)
            ret = self.ident
            while l < r:
                if l & 1:
                    ret = self.segfunc(ret, self.data[l])
                    l += 1
                if r & 1:
                    ret = self.segfunc(self.data[r - 1], ret)
                    r -= 1
                l >>= 1
                r >>= 1
            return ret

    N, Q = map(int, input().split())
    segtree = LazySegTree([0] * N)
    for _ in range(Q):
        q = list(map(int, input().split()))
        if q[0] == 0:
            s, t, x = q[1:]
            segtree.add(s+1, t+2, x)
        else:
            s, t = q[1:]
            print(segtree.query(s+1, t+2))


if __name__ == '__main__':
    main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
mod = 10 ** 9 + 7
INF = float('inf')

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()
lazyseg = Lazysegtree([0]*n, INF)
for _ in range(q):
    query = input().split()
    if query[0] == "0":  
        _, s, t, x = query
        s, t, x = map(int, [s, t, x])
        lazyseg.update(s, t+1, x)

    else:  
        _, s, t = query
        s, t = map(int, [s, t])
        print(lazyseg.query(s, t+1))

Solution (Python):



class SegmentTreeForRMQandRAQ:  
    def __init__(self, ls: list, segfunc=min, identity_element=2**31, lazy_ide=0):
        '''
        セグ木
        一次元のリストlsを受け取り初期化する。O(len(ls))
        区間のルールはsegfuncによって定義される
        identity elementは単位元。e.g., 最小値を求めたい→inf, 和→0, 積→1, gcd→0
        [単位元](https://ja.wikipedia.org/wiki/%E5%8D%98%E4%BD%8D%E5%85%83)
        '''
        self.ide = identity_element
        self.lide = lazy_ide  
        self.func = segfunc
        n = len(ls)
        self.num = 2 ** (n - 1).bit_length()  
        self.tree = [self.ide] * (2 * self.num)  
        self.lazy = [self.lide] * (2 * self.num)  
        for i, l in enumerate(ls):  
            self.tree[i + self.num - 1] = l
        for i in range(self.num - 2, -1, -1):  
            self.tree[i] = segfunc(self.tree[2 * i + 1], self.tree[2 * i + 2])

    def _gidx(self, l, r):
        '''
        lazy propagation用idx生成器 木の下から生成される。1based-indexなので注意.(使うときは-1するとか)
        もとの配列において[l,r)を指定したときに更新すべきidxをyieldする
        treesizeは多くの場合self.num
        '''
        L, R = l + self.num, r + self.num
        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 _lazyprop(self, *ids):
        '''
        遅延評価用の関数
        - self.tree[i] に self.lazy[i]の値を伝播させて遅延更新する
        - 子ノードにself.lazyの値を伝播させる **ここは問題ごとに書き換える必要がある**
        - self.lazy[i]をリセットする
        '''
        for i in reversed(ids):
            i -= 1  
            v = self.lazy[i]
            if v == self.lide:
                continue  
            
            
            self.tree[2 * i + 1] += v
            self.tree[2 * i + 2] += v
            self.lazy[2 * i + 1] += v
            self.lazy[2 * i + 2] += v
            self.lazy[i] = self.lide  

    def update(self, l, r, x):
        '''
        [l,r)番目の要素をxに変更する(木の中間ノードも更新する) O(logN)
        '''
        
        ids = tuple(self._gidx(l, r))
        
        
        if r <= l:
            return ValueError('invalid index (l,rがありえないよ)')
        l += self.num
        r += self.num
        while l < r:
            
            if r & 1:
                r -= 1
                self.tree[r - 1] += x
                self.lazy[r - 1] += x
            if l & 1:
                self.tree[l - 1] += x
                self.lazy[l - 1] += x
                l += 1
            l >>= 1
            r >>= 1
        
        for i in ids:
            i -= 1  
            self.tree[i] = self.func(  
                self.tree[2 * i + 1], self.tree[2 * i + 2]) + self.lazy[i]

    def query(self, l, r):
        '''
        区間[l,r)に対するクエリをO(logN)で処理する。例えばその区間の最小値、最大値、gcdなど
        '''
        if r <= l:
            return ValueError('invalid index (l,rがありえないよ)')
        
        self._lazyprop(*self._gidx(l, r))
        
        l += self.num
        r += self.num
        res = self.ide
        while l < r:  
            if r & 1:
                r -= 1
                res = self.func(res, self.tree[r - 1])
            if l & 1:
                res = self.func(res, self.tree[l - 1])
                l += 1
            l >>= 1
            r >>= 1  
        return res


n, q = map(int, input().split())
ls = [0] * n
seg = SegmentTreeForRMQandRAQ(ls)

for _ in range(q):
    cmd, *tmp = map(int, input().split())
    if cmd == 0:
        s, t, x = tmp
        seg.update(s, t + 1, x)
    else:
        s, t = tmp
        print(seg.query(s, t + 1))