ACL_データ構造
データ構造
Fenwick Tree fenwicktree BITと同じ コンストラクタfenwicktree.FenwickTree(n)$ O(n)
長さ$ n のものを構築する
添字は0, 1, ... n-1でok
加算.add(p, x)$ O(\log n)
A[p] += xする
総和.sum(l, r)$ O(\log n)
sum(A[l:r])を得る
二分探索はないので、自前で用意する。
Segtree セグ木 segtree
コンストラクタsegtree.SegTree(op, e, v)$ O(n)
引数：演算, 単位元, 初期値の配列
1点更新.set(p, x)$ O(\log n)
A[p] = xする
1点取得.get(p)$ O(1)
A[p]の値を得る
範囲取得.prod(l, r)$ O(\log n)
op(A[l:r])を得る
全範囲取得.all_prod()$ O(1)
op(A[:])を得る
右へ二分探索.max_right(l, f)$ O(\log n)
f( op( A[l:r] ) ) == Trueとなる最大のrを得る
左へ二分探索.min_left(r, f)$ O(\log n)
f( op( A[l:r] ) ) == Trueとなる最小のlを得る
Lazy Segtree 遅延セグ木 lazysegtree
実行速度が怪しいらしい
コンストラクタlazysegtree.LazySegTree(op, e, mapping, composition, id_, v)$ O(n)
引数：演算, 単位元, 作用素, 作用素の合成, 恒等写像, 初期値
1点更新.set(p, x)$ O(\log n)
A[p] = xする
1点取得.get(p)$ O(\log n)
A[p]の値を得る
範囲取得.prod(l, r)$ O(\log n)
op(A[l:r])を得る
全範囲取得.all_prod()$ O(1)
op(A[:])を得る
範囲更新.apply(l, r=None, f=None)$ O(\log n)
A[l:r]にfを作用させる
右へ二分探索.max_right(l, f)$ O(\log n)
f( op( A[l:r] ) ) == Trueとなる最大のrを得る
左へ二分探索.min_left(r, f)$ O(\log n)
f( op( A[l:r] ) ) == Trueとなる最小のlを得る
String 文字列 string
Suffix Array 接尾辞配列string.suffix_array(s, upper=None)$ O(n)や$ O(n\log n)や$ O(n+upper)
文字列 or 数値列sの Suffix Array を得る
s[sa[i]:] < s[sa[i+1]:]となる
LCP Array 最長共通接頭辞string.lcp_array(s, sa)$ O(n)
列sとその Suffix Arraysaから LCP Array を得る
lcp[i] := s[sa[i]:]とs[sa[i+1]:]の LCP の長さ
Z Algorithmstring.z_algorithm(s)$ O(n)
z[i] := s[0:]とs[i:]の LCP の長さ