0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

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

Posted at

はじめに

本記事は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には、これらの関数に与える引数が保存される。

mappingとcompositionの説明
引用: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)])

参考

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

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?