Veuillez me dire les points d'amélioration si vous le souhaitez.
#####segfunc#####
def segfunc(x, y):
return min(x, y)
#################
#####ide_ele#####
ide_ele = 2**31 - 1
#################
class LazySegmentTree:
"""
init(init_val, ide_ele):Array init_Initialiser avec val O(N)
update(l, r, x):section[l, r)Vers x O(logN)
query(l, r):section[l, r)Renvoie le segfunc de O(logN)
"""
def __init__(self, init_val, segfunc, ide_ele):
"""
init_val:Valeur initiale du tableau
segfunc:Opération que vous souhaitez créer une section
ide_ele:Élément d'unité
num:Puissance minimale de 2 supérieure ou égale à n
data:Tableau de valeurs(1-index)
lazy:Tableau de retard(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 = [None] * 2 * self.num
#Définissez la valeur du tableau sur la feuille
for i in range(n):
self.data[self.num + i] = init_val[i]
#Construire
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):
"""
Trouvez la section à propager
lm:Intervalle fermé maximal à gauche qui doit être propagé
rm:Section maximale ouverte à droite qui doit se propager
"""
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):
"""
Retarder le traitement de la propagation
ids:La section à propager
"""
for i in reversed(ids):
v = self.lazy[i]
if v is None:
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] = None
def update(self, l, r, x):
"""
section[l, r)Mettre à jour la valeur de à x
l, r: index(0-index)
x: update value
"""
*ids, = self.gindex(l, r)
self.propagates(*ids)
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])
def query(self, l, r):
"""
[l, r)Obtenez le 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
a = [1, 2, 3, 4, 5]
seg = LazySegmentTree(a, segfunc, ide_ele)
seg.update(1, 3, 0)
print(seg.(query(0, 3)))
#####segfunc#####
def segfunc(x, y):
return min(x, y)
#################
#####ide_ele#####
ide_ele = 2**31 - 1
#################
class LazySegmentTree:
"""
init(init_val, ide_ele):Array init_Initialiser avec val O(N)
add(l, r, x):section[l, r)Ajouter x à O(logN)
query(l, r):section[l, r)Renvoie le segfunc de O(logN)
"""
def __init__(self, init_val, segfunc, ide_ele):
"""
init_val:Valeur initiale du tableau
segfunc:Opération que vous souhaitez créer une section
ide_ele:Élément d'unité
num:Puissance minimale de 2 supérieure ou égale à n
data:Tableau de valeurs(1-index)
lazy:Tableau de retard(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
#Définissez la valeur du tableau sur la feuille
for i in range(n):
self.data[self.num + i] = init_val[i]
#Construire
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):
"""
Trouvez la section à propager
lm:Intervalle fermé maximal à gauche qui doit être propagé
rm:Section maximale ouverte à droite qui doit se propager
"""
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):
"""
Retarder le traitement de la propagation
ids:La section à propager
"""
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):
"""
section[l, r)Ajouter x à la valeur de
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)Obtenez le 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
Version non récursive du mémo d'implémentation de l'arborescence des segments d'évaluation retardée
Recommended Posts