library_for_python
This documentation is automatically generated by online-judge-tools/verification-helper
Dual Segment Tree
(Segment_Tree/Dual_Segment_Tree.py)
- View this file on GitHub
- Last update: 2025-05-23 00:45:05+09:00
Outline
モノイド $F=(F, \circ, 1_F)$ の列に対する区間更新, 1点取得を得意とするデータ構造
Contents
Constructer
S=Dual_Segment_Tree(L, comp, id)
- $L$ : $M$ の列
以下, $N:=\lvert L \rvert$ とする.
- $\mathrm{comp} : F \times F \to F; (\alpha, \beta) \mapsto \alpha \circ \beta$ : 二項演算.
- $\mathrm{id}$ : $F$ の単位元 $1_F$.
- 計算量 : $O(N)$ Time.
- (※ 現在, $L$ は無効である)
operate
S.operate(self, l, r, alpha, left_closed=True, right_closed=True)
- 第 $l$ 要素から第 $r$ 要素全てに対して, 左から $\alpha$ を作用させる.
-
left_close=Falseにすると, 左側が開区間になる (つまり, 左端が含まれなくなる).right_closeについても同様. -
制約
- 作用させる区間を $I$ としたとき, $I$ は $[0,N)$ に含まれる.
- $\alpha \in F$
- 計算量 : $O(\log N)$ Time.
get
S.get(k)
- 第 $k$ 要素を返す.
-
制約
- $0 \leq k \lt N$
- 計算量 : $O(\log N)$ Time.
refresh
B.refresh()
- 更新を遅延していた作用の記録を全て更新する.
- 計算量 : $O(N \log N)$ Time.
Verified with
Code
from typing import TypeVar, Generic, Callable
F = TypeVar('F')
class Dual_Segment_Tree(Generic[F]):
def __init__(self, A: list[F], comp: Callable[[F, F], F], id: F):
""" comp を演算とするリスト L の Dual Segment Tree を作成
comp : 作用素
id : 単位元
[注記]
更新は左から. つまり, comp(new, old) となる.
"""
self.__comp = comp
self.__id = id
N = len(A)
d = max(1, (N - 1).bit_length())
k = 1 << d
self.lazy = [self.id] * k + A + [self.id] * (k - N)
self.__size = k
@property
def comp(self) -> Callable[[F, F], F]:
return self.__comp
@property
def id(self) -> F:
return self.__id
@property
def size(self) -> int:
""" Dual Segment Tree の大きさ (扱える要素番号の最大値)
Returns:
int: Dual Segment Tree の大きさ
"""
return self.__size
#配列の第 m 要素を下に伝搬
def _propagate_at(self, m: int):
""" 遅延伝搬配列の第 m 要素を 1 個下の子に伝搬させる.
Args:
m (int): 要素番号
"""
lazy = self.lazy
if lazy[m] == self.id:
return
lazy[(m << 1) | 0] = self.comp(lazy[m], lazy[(m << 1) | 0])
lazy[(m << 1) | 1] = self.comp(lazy[m], lazy[(m << 1) | 1])
lazy[m] = self.id
#配列の第 m 要素より上を全て伝搬
def _propagate_above(self, m: int):
""" 遅延伝搬配列の第 m 要素の先祖 (自分自身除く) を根から順に伝搬させる.
Args:
m (int): 配列の番号
"""
for h in range(m.bit_length() - 1, 0, -1):
self._propagate_at(m >> h)
#作用
def action(self, l: int, r: int, alpha: F, left_closed: bool = True, right_closed: bool = True):
""" 第 l 要素から第 r 要素までの各要素に alpha を作用させる.
Args:
l (int): 左端
r (int): 右端
alpha (F): 作用させる値
left_closed (bool, optional): False にすると, 左端が開区間になる. Defaults to True.
right_closed (bool, optional): False にすると, 右端が開区間になる. Defaults to True.
"""
L = l + self.size + (not left_closed)
R = r + self.size + (right_closed)
L0 = R0 = -1
X, Y = L, R - 1
while X < Y:
if X & 1:
L0 = max(L0, X)
X += 1
if Y & 1 == 0:
R0 = max(R0, Y)
Y -= 1
X >>= 1
Y >>= 1
L0 = max(L0, X)
R0 = max(R0, Y)
self._propagate_above(L0)
self._propagate_above(R0)
lazy = self.lazy
comp = self.comp
while L < R:
if L & 1:
lazy[L] = comp(alpha, lazy[L])
L += 1
if R & 1:
R -= 1
lazy[R] = comp(alpha, lazy[R])
L >>= 1
R >>= 1
#リフレッシュ
def refresh(self):
""" 全ての遅延している伝搬を解除する.
"""
for m in range(1, self.size):
self._propagate_at(m)
#取得
def get(self, k: int) -> F:
""" 第 k 要素を取得する.
Args:
k (int): 要素の番号
Returns:
F: 第 k 要素
"""
m = k + self.size
self._propagate_above(m)
return self.lazy[m]
def __getitem__(self, index: int) -> F:
m = index + self.size
self._propagate_above(m)
return self.lazy[m]Traceback (most recent call last):
File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
raise NotImplementedError
NotImplementedError