遅延伝播セグメント木
Abstract
非再帰版の遅延伝播セグメント木 (Lazy propagation segment tree) を実装した.
Explanation
TODO そのうち書く.
Implementation
抽象化してある.
1-indexedで実装した.
非再帰で書いてある.
定数倍高速化を頑張ってる.
code:python
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
def __getitem__(self, i):
return self.fold(i, i+1)
def _build(self, lst):
# construction of a tree
# total 2 * self.N elements (tree0 is not used) e, N, op = self.e, self.N, self.op
tree = e * N + lst + e * (N - self.n) for i in range(N - 1, 0, -1):
lc, rc = i << 1, (i << 1)|1
treei = op(treelc, treerc) lengthi = lengthlc + lengthrc 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):
if x == identity: continue
lc, rc = k << 1, (k << 1) | 1
lazyk = identity # propagated # propagate self.v in a bottom-up manner
def _propagate_bottomup(self, indices):
v, op = self.v, self.op
# 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
left >>= 1; right >>= 1
while left < right:
if left & 1:
left += 1
if right & 1:
right -= 1
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.vleft is the right child left += 1
if right & 1: # self.vright-1 is the left child right -= 1
left >>= 1; right >>= 1
return op(L, R)
Verification
References