遅延セグ木 テンプレ集
まとめたいね
前提:import atcoder/lazysegtree
区間加算/区間min
code:nim
proc initRangeAddRangeMinSegtreeT(v:seqT):auto= type S = T
type F = T
proc op(a,b:S):S=min(a,b)
proc e():S=S(8e18)
proc mapping(f:F,x:S):S=f+x
proc composition(f,g:F):F=f+g
proc id():F=0
return LazySegTree.getType(S, F, op, e, mapping, composition, id).init(v)
区間加算/区間max
code:nim
proc initRangeAddRangeMaxSegtreeT(v:seqT):auto= type S = T
type F = T
proc op(a,b:S):S=max(a,b)
proc e():S=S(-8e18)
proc mapping(f:F,x:S):S=f+x
proc composition(f,g:F):F=f+g
proc id():F=0
return LazySegTree.getType(S, F, op, e, mapping, composition, id).init(v)
区間加算/区間min+min個数
code:nim
proc initRangeAddRangeMinSegtreeT(v:seqT):auto= type S = (T,int)
type F = T
proc op(a,b:S):S=
return a
else:
return b
proc e():S=(INF,1)
proc mapping(f:F,x:S):S=(x0+f,x1) proc composition(f,g:F):F=f+g
proc id():F=0
return LazySegTree.getType(S, F, op, e, mapping, composition, id).init(v.mapit((it,1)))
便利
区間加算/区間和
range affine range sum
code:nim
proc initrangeaffinerangesumT(v:seqT):auto= type S = (T,int)
type F = (T,T)
proc op(a,b:S):S=(a0+b0,a1+b1) proc e():S=(T(0),0)
proc mapping(f:F,x:S):S= (f0 * x0 + f1 * x1,x1) proc composition(f,g:F):F=(f0*g0,f0*g1+f1) proc id():F=(T(1),T(0))
return LazySegTree.getType(S, F, op, e, mapping, composition, id).init(v.mapit((it,1)))
区間加算 or 区間changeの上位互換
つよい。
区間clamp/区間min,max
code:nim
proc initclampsegtreeT(v:seqT):auto= type S = (T,T)
type F = (T,T,T)
proc op(a,b:S):S= (min(a0,b0),max(a1,b1)) proc e():S=(INF,-INF)
proc mapping(f:F,x:S):S= (max(f1,min(x0+f0,f2)),max(f1,min(x0+f1,f2))) proc composition(f,g:F):F= (g0+f0,max(f1,min(g1+f0,f2)),min(g2+f0,f2)) proc id():F=(0,-INF,INF)
return LazySegTree.getType(S, F, op, e, mapping, composition, id).init(v.mapit((it,it)))
ただし、作用はF=(a,b,c)として、min(c,max(b,x+a))
加算したいとき:(x,-INF,INF)を作用
chmaxしたいとき:(0,x,INF)を作用
chminしたいとき:(0,-INF,x)を作用
区間変更したいとき:(0,x,x)を作用
clampしたいとき:(0,l,r)を作用
返り値は(min,max)