Please tell me the improvement points if you like.
#####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_Initialize with val O(N)
update(l, r, x):section[l, r)To x O(logN)
query(l, r):section[l, r)Returns the segfunc of O(logN)
"""
def __init__(self, init_val, segfunc, ide_ele):
"""
init_val:Initial value of array
segfunc:Operation you want to make a section
ide_ele:Identity element
num:The smallest power of 2 greater than or equal to n
data:Value array(1-index)
lazy:Delay array(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
#Set the values of the array to the leaves
for i in range(n):
self.data[self.num + i] = init_val[i]
#Build
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):
"""
Find the section to be propagated
lm:Maximum left closed interval that needs to be propagated
rm:Maximum right-open interval that needs to propagate
"""
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):
"""
Delay propagation processing
ids:Interval of propagation target
"""
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)Update the value of to 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)Get the 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_Initialize with val O(N)
add(l, r, x):section[l, r)Add x to O(logN)
query(l, r):section[l, r)Returns the segfunc of O(logN)
"""
def __init__(self, init_val, segfunc, ide_ele):
"""
init_val:Initial value of array
segfunc:Operation you want to make a section
ide_ele:Identity element
num:The smallest power of 2 greater than or equal to n
data:Value array(1-index)
lazy:Delay array(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
#Set the values of the array to the leaves
for i in range(n):
self.data[self.num + i] = init_val[i]
#Build
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):
"""
Find the section to be propagated
lm:Maximum left closed interval that needs to be propagated
rm:Maximum right-open interval that needs to propagate
"""
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):
"""
Delay propagation processing
ids:Interval of propagation target
"""
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)Add x to the value of
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)Get the 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
Non-recursive version of lazy evaluation segment tree implementation memo
Recommended Posts