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

Solution code:
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:
    #RAQ
    def __init__(self, A, intv, initialize=True, segf=min):
        #区間は 1-indexed で管理
        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":  # add
        _, s, t, x = query
        s, t, x = map(int, [s, t, x])
        lazyseg.update(s, t+1, x)

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

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_2_H


class SegmentTreeForRMQandRAQ:  # range minimum query and range add query
    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  # lazy用単位元
        self.func = segfunc
        n = len(ls)
        self.num = 2 ** (n - 1).bit_length()  # n以上の最小の2のべき乗
        self.tree = [self.ide] * (2 * self.num)  # 関係ない値を-1においてアクセスを許すと都合が良い
        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:  # Rでもいいけどね
            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  # 0basedindexに修正
            v = self.lazy[i]
            if v == self.lide:
                continue  # 単位元ならする必要のNASA
            # どうやって遅延更新するかは問題によってことなる
            # 今回なら範囲(最小値を持つ)に加算なので、そのままvを加算すればよい
            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)
        '''
        # 1, 根から区間内においてlazyの値を伝播しておく(self.treeの値が有効になる)
        ids = tuple(self._gidx(l, r))
        # self._lazyprop(*ids)  # 足し算はlazyに対し込んでも良いのでupdate時にpropしなくても良い
        # 2, 区間に対してtree,lazyの値を更新 (treeは根方向に更新するため、lazyはpropで葉方向に更新するため)
        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
        # 3, 伝播させた区間について下からdataの値を伝播する
        for i in ids:
            i -= 1  # to 0based
            self.tree[i] = self.func(  # ここでlazyの値を考慮しなければ行けない
                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がありえないよ)')
        # 1, 根からにlazyの値を伝播させる
        self._lazyprop(*self._gidx(l, r))
        # 2, 区間[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))

Submission status: Accepted

Solution code:
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 # binary operation of elements
        self.apply = apply # function to apply to an element
        self.comp = comp # composition of functions
        self.e = e # identity element w.r.t. op
        self.identity = identity # identity element w.r.t. comp
        self.v, self.length = self._build(lst) # self.v is set to be 1-indexed for simplicity
        self.lazy = [self.identity] * (2 * self.N)
    
    def __getitem__(self, i):
        return self.fold(i, i+1)
    
    def _build(self, lst):
        # construction of a tree
        # total 2 * self.N elements (tree[0] is not used)
        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
    
    # propagate self.lazy and self.v in a top-down manner
    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 # propagated

    # propagate self.v in a bottom-up manner
    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])

    # update for the query interval [l, r) with function x
    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
        
        # update self.v and self.lazy for the query interval [l, r)
        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)
    
    # returns answer for the query interval [l, r)
    def fold(self, l, r):
        self._propagate_topdown(*self._indices(l, r))
        
        e, N, v, op = self.e, self.N, self.v, self.op
        
        # calculate the answer for the query interval [l, r)
        left = l + N; right = r + N
        L = R = e
        while left < right:
            if left & 1: # self.v[left] is the right child
                L = op(L, v[left])
                left += 1
            if right & 1: # self.v[right-1] is the left child
                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)))

Submission status: Accepted

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

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

seg_el=1<<(N.bit_length()) # Segment treeの台の要素数
SEG=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化
LAZY=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

def indexes(L,R): # 遅延伝搬すべきノードのリストを返す. （つまり, updateやgetvaluesで見るノードより上にあるノードたち）
    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,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,r)に関するminを調べる

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

Submission status: Accepted

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

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)

    # 伝搬される区間のインデックス(1-indexed)を全て列挙するgenerator
    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):
        # 1-indexedで単調増加のインデックスリスト
        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を加算 """

        # 1. lazyの値は伝搬させない
        # 2. 区間[l,r)のdata, lazyの値を更新
        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
        # 3. 更新される区間を部分的に含んだ区間のdataの値を更新 (lazyの値を考慮)
        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)の最小値を取得 """

        # 1. トップダウンにlazyの値を伝搬
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r

        # 2. 区間[l, 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))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
class Lazysegtree:
    #RAQ
    def __init__(self, A, intv, initialize = True, segf = min):
        #区間は 1-indexed で管理
        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)))

Submission status: Accepted

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