はじめに

本記事は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)])

参考

以下を参照し記事を書きました。より詳しいことが知りたい場合も参考になると思います。