【データ構造編】ac-Library-pythonを軽くまとめる

# はじめに
本記事は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
```python
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)$

<details><summary>使用例</summary><div>

```python
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
```

</div></details>

## SegTree
```python 
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)$


<details><summary>使用例</summary><div>

```python
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
```

</div></details>

## LazySegTree
```python
from atcoder.lazysegtree import LazySegTree
```
:::note warn
2024/03/05時点では[ac-library-python](https://github.com/not522/ac-library-python/blob/master/README_ja.md)に以下の表記があります。
>移植は完了していますが、まだバグが残っている可能性があります。また、modintやlazysegtreeなどのライブラリは速度の改善が必要です。
:::
segTreeに、操作`f`を記録し必要な時に行うという処理を追加したもので、より高速である。一つのノードはdataと操作を記録するlazyを持つ。segTreeと比べ、区間に対し同一の操作を行うとき有用。
操作を記録する方法は、`mapping`,`composition`が実際の操作にあたる。`lazy`には、これらの関数に与える引数が保存される。

![mappingとcompositionの説明](https://cdn-ak.f.st-hatena.com/images/fotolife/b/betrue12/20200922/20200922195827.png)
引用：[AtCoder LibraryのLazy Segtreeの使い方](https://betrue12.hateblo.jp/entry/2020/09/22/194541)

* __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
:::note info
2024/03/06時点で `g: Any`と表記されていますが、
`g:Callable[[Any], bool]`が適切です。動作に影響はありません。
:::
`g`を満たす区間[`left`,`right`)となる`left`を返す
`g`:一つの引数（要素）を取り、`bool`値を返す関数。単位元に対し`True`を返す。
 計算量:$O(\log n)$


<details><summary>使用例</summary><div>

操作は、$[l,r)$の値を$[l,r)の最大値+1$となるように更新します。
積の計算では、$[l,r)$における最大値を求めたいと思います。
$1 \leq l,r \leq 10$とします。


```python
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

```

</div></details>

## Stringアルゴリズム
```python
from atcoder.string import {function}
```
二分探索を用いた文字列検索や、[相異なる部分文字列の数を求める計算](https://drken1215.hatenablog.com/entry/2022/12/15/022900)に有効。
* suffix_array(s: Union[str, List[int]], upper: Optional[int] = None) → List[int]
長さ$n$の文字列$s$の[Suffix Array](https://ja.wikipedia.org/wiki/%E6%8E%A5%E5%B0%BE%E8%BE%9E%E9%85%8D%E5%88%97)として、長さ$n$の$vector$を返す
* lcp_array(s: Union[str, List[int]], sa: List[int]) → List[int]
長さ$n$の文字列$s$の[LCP Array](https://ja.wikipedia.org/wiki/%E6%8E%A5%E5%B0%BE%E8%BE%9E%E9%85%8D%E5%88%97)として、長さ$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`の戻り値

<details><summary>使用例</summary><div>

二分探索を用いた文字列検索を実装します
```python
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)])
```

</div></details>

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

https://github.com/not522/ac-library-python/tree/master

https://atcoder.github.io/ac-library/production/document_ja/

https://ac-library-python.readthedocs.io/en/latest/index.html

https://betrue12.hateblo.jp/entry/2020/09/22/194541