library_for_python
This documentation is automatically generated by online-judge-tools/verification-helper
Segment Tree
(Segment_Tree/Segment_Tree.py)
- View this file on GitHub
- Last update: 2025-02-22 11:32:25+09:00
Outline
モノイド $M=(M, *, e_M)$ の列に対する1点更新, 区間積の取得を得意とするデータ構造
Contents
Constructer
S=Segment_Tree(L, calc, unit)
- $L$ : $M$ の列
以下, $N:=\lvert L \rvert$ とする.
- $\operatorname{calc} : M \times M \to M; (x,y) \mapsto x * y$ : 二項演算.
- $\mathrm{unit}$ : $M$ の単位元 $e_M$.
- 計算量 : $O(N \log N)$ Time.
get
S.get(k)
- 第 $k$ 要素を返す.
-
制約
- $0 \leq k \lt N$
- 計算量 : $O(1)$ Time.
update
S.update(k,x)
- 第 $k$ 要素を $x$ に変更する.
-
制約
- $0 \leq k \lt N$
- $x \in M$
- 計算量 : $O(\log N)$ Time.
product
B.product(l, r)
- $B_l * B_{l+1} * \dots * B_r$ を求める ( $l \gt r$ の場合は $e_M$ とする).
-
制約
- $0 \leq l \lt N$
- $0 \leq r \lt N$
- 計算量 : $O(\log N)$ Time.
all_sum
B.all_product(k)
- $B_0 * B_1 * \dots * B_{N-1}$ を求める.
- 計算量 : $O(1)$ Time.
max_right
B.max_right(left, cond)
- 以下の2条件を共に満たすような $r$ のうちの1つを返す.
- $r={\rm left}$ または $\operatorname{cond}(B_{ {\rm left}} * B_{ {\rm left}+1} * \dots * B_{r-1})=\mathbb{T}$
- $r=N$ または $\operatorname{cond}(B_{ {\rm left}} * B_{ {\rm left}+1} * \dots * B_r)=\mathbb{F}$
- 特に, $\operatorname{cond}$ が単調減少のときは, 整数 $r$ は $\operatorname{cond}(B_{ {\rm left}} * B_{ {\rm left}+1} * \dots * B_{r-1})=\mathbb{T}$ を満たす最大の整数となる.
-
制約
- $0 \leq {\rm left} \leq N$
- $\operatorname{cond}: G \to \{\mathbb{T}, \mathbb{F} \}$
- 計算量 : $O(\log N)$ Time.
min_left
B.min_left(right, cond)
- 以下の2条件を共に満たすような $l$ のうちの1つを返す.
- $l={\rm right}$ または $\operatorname{cond}(B_l * B_{l+1} * \dots * B_{ {\rm right}-1})=\mathbb{T}$
- $l=0$ または $\operatorname{cond}(B_{l-1} * B_l * \dots * B_{ {\rm right}-1})=\mathbb{F}$
- 特に, $\operatorname{cond}$ が単調増加のときは, 整数 $l$ は $\operatorname{cond}(B_l * B_{l+1} * \dots * B_{ {\rm right}-1})=\mathbb{T}$ を満たす最小の整数となる.
-
制約
- $0 \leq {\rm right} \leq N$
- $\operatorname{cond}: G \to \{\mathbb{T}, \mathbb{F} \}$
- 計算量 : $O(\log N)$ Time.
Verified with
Code
from typing import TypeVar, Generic, Callable, Iterator
M = TypeVar('M')
class Segment_Tree(Generic[M]):
def __init__(self, L: list[M], op: Callable[[M, M], M], unit: M):
""" op を演算とする初期状態 L の Segment Tree を生成する.
Args:
L (list[M]): 初期状態
op (Callable[[M, M], M]): 演算
unit (M): M の単位元
"""
self.op=op
self.unit=unit
N=len(L); self.n=N
d=max(1,(N-1).bit_length())
k=1<<d
self.data=data=[unit]*k+L+[unit]*(k-len(L))
self.N=k
self.depth=d
for i in range(k-1,0,-1):
data[i]=op(data[i<<1], data[i<<1|1])
def get(self, k: int) -> M:
""" 第 k 要素を取得する.
Args:
k (int): 要素の場所
Returns:
M: 第 k 要素
"""
assert 0<=k<self.N,"添字が範囲外"
return self.data[k+self.N]
def update(self, k: int, x: M) -> None:
""" 第 k 要素を x に変え, 更新する.
Args:
k (int): 要素の場所
x (M): 更新後の第 k 要素
"""
assert 0<=k<self.N,"添字が範囲外"
m=k+self.N
data=self.data; op=self.op
data[m]=x
while m>1:
m>>=1
data[m]=op(data[m<<1], data[m<<1|1])
def product(self, l: int, r: int, left_closed: bool = True, right_closed: bool = True) -> M:
""" 第 l 要素から第 r 要素までの総積を求める.
Args:
l (int): 左端
r (int): 右端
left_closed (bool, optional): False にすると, 左端が開区間になる. Defaults to True.
right_closed (bool, optional): False にすると, 右端が開区間になる. Defaults to True.
Returns:
M: 第 l 要素から第 r 要素までの積
"""
L=l+self.N+(not left_closed)
R=r+self.N+(right_closed)
vL=self.unit
vR=self.unit
data=self.data; op=self.op
while L<R:
if L&1:
vL=op(vL, data[L])
L+=1
if R&1:
R-=1
vR=op(data[R], vR)
L>>=1
R>>=1
return op(vL,vR)
def all_product(self) -> M:
return self.data[1]
def max_right(self, left: int, cond: Callable[[int], bool]) -> int:
""" 以下の2つをともに満たす r の1つを返す.\n
(1) r=left or cond(data[left]*data[left+1]*...*data[r-1]): True\n
(2) r=N or cond(data[left]*data[left+1]*...*data[r]): False\n
※ cond が単調減少の時, cond(data[left]*...*data[r-1]) を満たす最大の r となる.\n
※ cond(unit) = True を課す.
Args:
left (int): 左端
cond (Callable[[int], bool]): 条件
Returns:
int: r
"""
assert 0<=left<=self.N,"添字が範囲外"
assert cond(self.unit),"単位元が条件を満たさない."
if left==self.N:
return self.N
left+=self.N
sm=self.unit
op=self.op; data=self.data
first=True
while first or (left & (-left))!=left:
first=False
while left%2==0:
left>>=1
if not cond(op(sm, data[left])):
while left<self.N:
left<<=1
if cond(op(sm, data[left])):
sm=op(sm, data[left])
left+=1
return left-self.N
sm=op(sm, data[left])
left+=1
return self.N
def min_left(self, right: int, cond: Callable[[int], bool]) -> int:
""" 以下の 2 つをともに満たす l の1つを返す.\n
(1) l=right or cond(data[l]*data[l+1]*...*data[right-1]): True\n
(2) l=0 or cond(data[l-1]*data[l]*...*data[right-1]): False\n
※ cond が単調増加の時, cond(data[l]*...*data[right-1]) を満たす最小の l となる.\n
※ cond(unit) = True を課す.
Args:
right (int): 右端
cond (Callable[[int], bool]): 条件
Returns:
int: l
"""
assert 0<=right<=self.N,"添字が範囲外"
assert cond(self.unit),"単位元が条件を満たさない."
if right==0:
return 0
right+=self.N
sm=self.unit
op=self.op; data=self.data
first=1
while first or (right & (-right))!=right:
first=0
right-=1
while right>1 and right&1:
right>>=1
if not cond(op(data[right], sm)):
while right<self.N:
right=2*right+1
if cond(op(data[right], sm)):
sm=op(data[right], sm)
right-=1
return right+1-self.N
sm=op(data[right], sm)
return 0
def __getitem__(self, k: int) -> M:
return self.get(k)
def __setitem__(self, k: int, x: M) -> None:
return self.update(k,x)
def __iter__(self) -> Iterator[M]:
for i in range(self.n):
yield self.get(i)Traceback (most recent call last):
File "/opt/hostedtoolcache/Python/3.13.3/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.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
raise NotImplementedError
NotImplementedError