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



Sample input:
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:
-2
0
1
-1

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# DSL_2_H: RMQ and RAQ
# Range Minimum Query and Range Add Query
# Lazy propagate segment tree

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 = [0] * self.size
        self.lazy = [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 j < lo or i > hi:
                if lz:
                    data[r] += lz
                    if i < j:
                        lazy[left] += lz
                        lazy[right] += lz
            elif 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
                lv = _add(left, i, mid, lz)
                rv = _add(right, mid+1, j, lz)

                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 j < lo or i > hi:
                if lz and i < j:
                    lazy[left] += lz
                    lazy[right] += lz
                return self.MAXV
            elif lo <= i and j <= hi:
                if lz and i < j:
                    lazy[left] += lz
                    lazy[right] += lz
                return data[r]
            else:
                mid = (i + j) // 2
                lv = _min(left, i, mid, lz)
                rv = _min(right, mid+1, j, lz)
                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 = [int(i) for i in args]
            tree.add(s, t, x)
        elif com == '1':
            s, t = [int(i) for i in 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()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# DSL_2_H: RMQ and RAQ
# Range Minimum Query and Range Add Query
# Lazy propagate segment tree

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 = [0] * self.size
        self.lazy = [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 j < lo or i > hi:
                if lz:
                    data[r] += lz
                    if i < j:
                        lazy[left] += lz
                        lazy[right] += lz
            elif 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
                lv = _add(left, i, mid, lz)
                rv = _add(right, mid+1, j, lz)

                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 j < lo or i > hi:
                if lz and i < j:
                    lazy[left] += lz
                    lazy[right] += lz
                return self.MAXV
            elif lo <= i and j <= hi:
                if lz and i < j:
                    lazy[left] += lz
                    lazy[right] += lz
                return data[r]
            else:
                mid = (i + j) // 2
                lv = _min(left, i, mid, lz)
                rv = _min(right, mid+1, j, lz)
                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()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# DSL_2_H: RMQ and RAQ
# Range Minimum Query and Range Add Query
# Lazy propagate segment tree

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 = [0] * self.size
        # self.lazy = [0] * self.size
        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 j < lo or i > hi:
                if lz:
                    data[r] += lz
                    if i < j:
                        lazy[left] += lz
                        lazy[right] += lz
            elif 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
                lv = _add(left, i, mid, lz)
                rv = _add(right, mid+1, j, lz)

                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 j < lo or i > hi:
                if lz and i < j:
                    lazy[left] += lz
                    lazy[right] += lz
                return self.MAXV
            elif lo <= i and j <= hi:
                if lz and i < j:
                    lazy[left] += lz
                    lazy[right] += lz
                return data[r]
            else:
                mid = (i + j) // 2
                lv = _min(left, i, mid, lz)
                rv = _min(right, mid+1, j, lz)
                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()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# DSL_2_H: RMQ and RAQ
# Range Minimum Query and Range Add Query
# Lazy propagate segment tree

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

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

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

        # print(qi,ras.A,ras.B)

    return JA(rr, "\n")

# start = time.time()
print(main())
# pe(time.time() - start)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
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_composite(
            #     action, action_table[i * 2])
            # action_table[i * 2 + 1] = action_composite(
            #     action, action_table[i * 2 + 1])
            action_table[i * 2] += action
            action_table[i * 2 + 1] += action
            action_table[i] = action_unity
            # value_table[i * 2] = action_force(
            #     action, value_table[i * 2], size)
            # value_table[i * 2 + 1] = action_force(
            #     action, value_table[i * 2 + 1], size)
            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)

    # print("action", file=sys.stderr)
    # debugprint(action_table)
    # print("value", file=sys.stderr)
    # debugprint(value_table)
    # print(file=sys.stderr)

    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():
    # parse input
    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:
            # add
            s, t, value = args
            lazy_range_update(
                action_table, value_table, s, t + 1,
                value, composite, force, action_unity, value_binop)

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


# tests
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()

Submission status: Accepted

Solution code:
#####segfunc#####
def segfunc(x, y):
    return min(x, y)
#################

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

Submission status: Accepted

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

Submission status: Accepted

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

    class LazySegTree:
        # Range add query
        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

        # open interval [l, r)
        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)

        # open interval [l, r)
        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()