はじめに
本記事はac-Library-pythonを使用するにあたり、引数やメソッド・計算量など最低限の情報をまとめたもののデータ構造編になります。
「ドキュメントが小難しく読んでいられない・結局どういうこと?」といった人を対象としています。
データ構造
p
,left
,right
などの位置を表す引数は0-index
です。
単位元とは、二項演算op
を行う際、結果に影響しないような値です。例としてこのような値があります。
二項演算 | 関数 | 単位元 |
---|---|---|
最小値 | min(x,y) | float('inf') |
最大値 | max(x,y) | -float('inf') |
区間和 | x+y | 0 |
区間積 | x*y | 1 |
最大公約数 | math.gcd(x,y) | 0 |
FenwickTree
from atcoder.fenwicktree import FenwickTree
長さ$n$の配列に対し区間の要素の総和を$O(\log n)$で計算できる。配列の操作と和の計算を行う場合に有用。
-
init(n: int = 0) → None
n
:数列の大きさ
計算量:$O(n)$ -
add(p: int, x: Any) → None
p
の値をx
で上書き
計算量:$O(\log n)$ -
sum(left: int, right: int) → Any
[left
,right
)の合計値を返す
計算量:$O(\log n)$
使用例
from atcoder.fenwicktree import FenwickTree
#数列を定義
a = [0,1,2,3,4,5,6,7,8,9]
#インスタンス化
fenwick_tree = FenwickTree(n=len(a))
#データの追加
for i,ai in enumerate(a):
fenwick_tree.add(i,ai)
#区間和の取得
print(fenwick_tree.sum(1,3))
#>>3
SegTree
from atcoder.segtree import SegTree
長さ$n$の配列に対し区間の要素の総積を$O(\log n)$で計算できる。積の計算と配列の操作を行う場合に有用。
-
init(op: Callable[[Any, Any], Any], e: Any, v: Union[int, List[Any]]) → None
op
:積の計算をする関数。型Xの引数を2つとり、型Xの戻り値を持つ
e
:単位元
v
:整数または型自由な要素のリスト
計算量:$O(n)$ -
set(p: int, x: Any) → None
p
の値をx
に更新
計算量:$O(\log n)$ -
get(p: int) → Any
p
の値を取得
計算量:$O(1)$ -
prod(left: int, right: int) → Any
[left
,right
)に対するop
の結果を返す
計算量:$O(\log n)$ -
all_prod() → Any
prod
を、全区間に対して行う
計算量:$O(1)$ -
max_right(left: int, f: Callable[[Any], bool]) → int
f
を満たす区間[left
,right
)となるright
を返す
f
:1つの引数(要素)を取り、bool
値を返す関数。単位元に対しTrue
を返す。
計算量:$O(\log n)$ -
min_left(right: int, f: Callable[[Any], bool]) → int
f
を満たす区間[left
,right
)となるleft
を返す
f
:1つの引数(要素)を取り、bool
値を返す関数。単位元に対しTrue
を返す。
計算量:$O(\log n)$
使用例
from atcoder.segtree import SegTree
#数列を定義
a = [0,1,2,3,4,5,6,7,8,9]
#インスタンス化
seg_tree =SegTree(op=max,e=-1,v=a)
#区間のop(=max)を取得
print(seg_tree.prod(0,5))
#>>4
#値の更新
seg_tree.set(6,100)
#値の取得
print(seg_tree.get(6))
#>>100
#全区間のop(=max)を取得
print(seg_tree.all_prod())
#>>100
#条件を満たし続けるrightのインデックスを取得
print(seg_tree.max_right(1,lambda x: x<10))
#>>6
#条件を満たし続けるleftのインデックスを取得
print(seg_tree.min_left(8,lambda x: x<10))
#>>7
LazySegTree
from atcoder.lazysegtree import LazySegTree
2024/03/05時点ではac-library-pythonに以下の表記があります。
移植は完了していますが、まだバグが残っている可能性があります。また、modintやlazysegtreeなどのライブラリは速度の改善が必要です。
segTreeに、操作f
を記録し必要な時に行うという処理を追加したもので、より高速である。一つのノードはdataと操作を記録するlazyを持つ。segTreeと比べ、区間に対し同一の操作を行うとき有用。
操作を記録する方法は、mapping
,composition
が実際の操作にあたる。lazy
には、これらの関数に与える引数が保存される。
引用:AtCoder LibraryのLazy Segtreeの使い方
-
init(op: Callable[[Any, Any], Any], e: Any, mapping: Callable[[Any, Any], Any], composition: Callable[[Any, Any], Any], id_: Any, v: Union[int, List[Any]]) → None
op
:積の計算をする関数。型Xの引数を2つとり、型Xの戻り値を持つ
e
:単位元
mapping(f,data)
:親lazyに記録した操作f
を子のdataに適応する関数
composition(f,g)
:親lazyに記録した操作f
を子lazyの操作g
に追加する関数
id_
:mapping(id
,data)=dataとなる値
v
:整数または型自由な要素のリスト -
set(p: int, x: Any) → None
p
の値をx
に更新
計算量:$O(\log n)$ -
get(p: int) → Any
p
の値を取得
計算量:$O(\log n)$ -
prod(left: int, right: int) → Any
[left
,right
)に対するop
の結果を返す
計算量:$O(\log n)$ -
all_prod() → Any
prod
を、全区間に対して行う
計算量:$O(1)$ -
apply(left: int, right: Optional[int] = None, f: Optional[Any] = None) → None
[left
,right
)に操作f
を行う
計算量:$O(\log n)$ -
max_right(left: int, g: Callable[[Any], bool]) → int
g
を満たす区間[left
,right
)となるright
を返す
g
:一つの引数(要素)を取り、bool
値を返す関数。単位元に対しTrue
を返す。
計算量:$O(\log n)$ -
min_left(right: int, g: Any) → int
2024/03/06時点で g: Any
と表記されていますが、
g:Callable[[Any], bool]
が適切です。動作に影響はありません。
g
を満たす区間[left
,right
)となるleft
を返す
g
:一つの引数(要素)を取り、bool
値を返す関数。単位元に対しTrue
を返す。
計算量:$O(\log n)$
使用例
操作は、$[l,r)$の値を$[l,r)の最大値+1$となるように更新します。
積の計算では、$[l,r)$における最大値を求めたいと思います。
$1 \leq l,r \leq 10$とします。
from atcoder.lazysegtree import LazySegTree
#opの定義(あえて記述しています)
def op(n1,n2):
return max(n1,n2)
#単位元の定義
e=-1
#mappingの定義
def mapping(f:int,data:int):
#操作が単位元であれば、dataのままで良い
if f == e:
return data
else:
#dataの値に関係なく上書きする
return f
#compositionの定義
def composition(f,g):
if f == e:
return g
else:
#子の更新に関係なく親の値を受け取る
return f
#id_を定義
id_ = -1
#初期値を定義
v = [0]*10
#[0,0,0,0,0,0,0,0,0,0]
#インスタンス化
lazy_seg_tree = LazySegTree(op,e,mapping,composition,id_,v)
#値の更新
lazy_seg_tree.set(3,1)
#[0,0,0,1,0,0,0,0,0,0]
#値の取得
print(lazy_seg_tree.get(3))
#>>1
#区間のopを取得
max_height = lazy_seg_tree.prod(0,4)
print(max_height)
#>>1
#区間にその区間の最大値+1の値を入れる
lazy_seg_tree.apply(0,4,max_height+1)
#[2,2,2,2,0,0,0,0,0,0]
#全区間のopを取得
print(lazy_seg_tree.all_prod())
#>>2
#条件を満たし続けるrightのインデックスを取得
print(lazy_seg_tree.max_right(1 ,lambda x: x<1))
#>>1
#条件を満たし続けるleftのインデックスを取得
print(lazy_seg_tree.min_left(8,lambda x: x<1))
#>>4
Stringアルゴリズム
from atcoder.string import {function}
二分探索を用いた文字列検索や、相異なる部分文字列の数を求める計算に有効。
- suffix_array(s: Union[str, List[int]], upper: Optional[int] = None) → List[int]
長さ$n$の文字列$s$のSuffix Arrayとして、長さ$n$の$vector$を返す - lcp_array(s: Union[str, List[int]], sa: List[int]) → List[int]
長さ$n$の文字列$s$のLCP Arrayとして、長さ$n−1$の配列を返す。 - z_algorithm(s: Union[str, List[int]]) → List[int]
入力の長さを$n$として、長さ$n$の配列を返す。$i$番目の要素は$s[0,n)$とs$[i,n)$のlcpの長さ
s
:文字列または整数のリスト
upper
:s
が整数リストの時、その最大値を指定できる。定義域外はエラー。
sa
:suffix_array
の戻り値
使用例
二分探索を用いた文字列検索を実装します
from atcoder.string import suffix_array
#ターゲットの文字列と、装飾する文字列を定義
random1 = "aljkdsjafoekdsfjowesdafawo;edkjfje;ojgadjfjeo'aksdfje"
random2 = "oaewjgoandkfeoijgaodngmanveoganweoifdnvr;ibn;vknveann"
mississippi = "mississippi"
s = random1+mississippi+random2
#suffix_arrayを作成
sa = suffix_array(s)
#二分探索を定義
def find_mississippi(s,sa,target,index,left,right):
if s[sa[index]:]<target:#右に答えがあることを判定する
if right-index == 1:#右隣で左と判定し、今右と判定している=間のものが答え
return index+1
index,left=(index+right)//2,index
return find_mississippi(s,sa,target,index,left,right)
else:#左に答え
index,right=(index+left)//2,index
return find_mississippi(s,sa,target,index,left,right)
#indexをもとに、探索文字列を表示
result = find_mississippi(s,sa,mississippi,len(sa)//2,0,len(sa))
print(s[sa[result]:sa[result]+len(mississippi)])
参考
以下を参照し記事を書きました。より詳しいことが知りたい場合も参考になると思います。