Bitte teilen Sie mir die Verbesserungspunkte mit, wenn Sie möchten.
#####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_Initialisieren Sie mit Wert O.(N)
update(l, r, x):Sektion[l, r)Zu x O.(logN)
query(l, r):Sektion[l, r)Gibt den Segfunc von O zurück(logN)
"""
def __init__(self, init_val, segfunc, ide_ele):
"""
init_val:Anfangswert des Arrays
segfunc:Operation, für die Sie einen Abschnitt erstellen möchten
ide_ele:Einheitselement
num:Mindestleistung von 2 größer oder gleich n
data:Wertearray(1-index)
lazy:Array verzögern(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
#Setzen Sie den Wert des Arrays auf das Blatt
for i in range(n):
self.data[self.num + i] = init_val[i]
#Bauen
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):
"""
Suchen Sie den Abschnitt, der weitergegeben werden soll
lm:Maximales linkes geschlossenes Intervall, das weitergegeben werden muss
rm:Maximaler rechtsoffener Abschnitt, der sich ausbreiten muss
"""
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):
"""
Verarbeitung der Verzögerung der Weitergabe
ids:Der zu propagierende Abschnitt
"""
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):
"""
Sektion[l, r)Aktualisieren Sie den Wert von auf 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)Holen Sie sich die 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_Initialisieren Sie mit Wert O.(N)
add(l, r, x):Sektion[l, r)Addiere x zu O.(logN)
query(l, r):Sektion[l, r)Gibt den Segfunc von O zurück(logN)
"""
def __init__(self, init_val, segfunc, ide_ele):
"""
init_val:Anfangswert des Arrays
segfunc:Operation, für die Sie einen Abschnitt erstellen möchten
ide_ele:Einheitselement
num:Mindestleistung von 2 größer oder gleich n
data:Wertearray(1-index)
lazy:Array verzögern(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
#Setzen Sie den Wert des Arrays auf das Blatt
for i in range(n):
self.data[self.num + i] = init_val[i]
#Bauen
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):
"""
Suchen Sie den Abschnitt, der weitergegeben werden soll
lm:Maximales linkes geschlossenes Intervall, das weitergegeben werden muss
rm:Maximaler rechtsoffener Abschnitt, der sich ausbreiten muss
"""
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):
"""
Verarbeitung der Verzögerung der Weitergabe
ids:Der zu propagierende Abschnitt
"""
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):
"""
Sektion[l, r)Addiere x zum Wert von
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)Holen Sie sich die 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
Nicht rekursive Version des Memos zur Implementierung eines verzögerten Bewertungssegmentbaums
Recommended Posts