sortedcontainers
SortedSet, SortedList, SortedDictの 3 つがある。
C++ では SortedSetがstd::set、SortedListがstd::multiset、SortedDictがstd::map（らしい）
計算量は配列サイズ $ N のときのもの、$ O(\log{N})+ := O(\log{N} + M + \frac{N}{M^2}) とする。
$ M は _load = 1000 と設定されている定数。$ M = \sqrt{N} か$ M = \sqrt[3]{N} がいいらしい。
そのままでも十分だと思うが、 _load の値を変更したい場合は ._reset(load=200) などとする。
set の関数や sequence の関数がほぼそのまま使える
x in S for x in S len(S) reversed(S) S - T S & T S ^ T S | T copy(S)
S[i] で i 番目に小さい値が得られる
S[i] del S[i] S.pop(i) : $ O(\log{N})+ でできちゃう
初期化 S = SortedSet(iterable=None, key=None) $ O(N\log{N})
配列 iterable で初期化
関数 key で比較する
反転はできないため、「i番目に大きい値」→「~i番目に小さい値」などで言い換えて対処すること
値の追加 S.add(x) $ O(\log{N})+
値を複数追加 S.update([x, y, ...]) $ O(k\log{N})+
値の削除 S.discard(x) $ O(\log{N})+
x not in S のときは何もしない
値の削除 S.remove(x) $ O(\log{N})+
x not in S のときは Error
count S.count(x) $ O(1)
二分探索 S.bisect_left(x) S.bisect_right(x) $ O(\log{N})+
index S.index(x, l=None, r=None) $ O(\log{N})+
[l:r] の範囲内で x が最初に出てくる index を得る
x not in S[l:r] のときは Error
irange S.irange(minimum=None, maximum=None, inclusive=(True, True), reverse=False)
minimum 以上 maximum 以下の値を順に得るイテレータ
inclusiveは端の値を含めるか否か。(True, False) とすれば半開区間 $ [\min, \max) にできる
sequence の関数がほぼそのまま使える
for x in L reversed(L) len(L) L == A L != A L < A copy(L)
L[i] で i 番目に小さい値が得られる
x in L : $ O(\log{N}) でできちゃう
L[i] del L[i] L.count(x) : $ O(\log{N})+
L + A L * a : $ O(N\log{N})
追加は append extend ではなく add update となる点に注意
List というより MultiSet なイメージ
変更も L[i] = x とはできず、del L[i] からの L.add(x) とする必要がある
初期化 L = SortedList(iterable=None, key=None) $ O(N\log{N})
配列 iterable で初期化
関数 key で比較する
反転はできないため、「i番目に大きい値」→「~i番目に小さい値」などで言い換えて対処すること
値の追加 L.add(x) $ O(\log{N})+
値を複数追加 L.update([x, y, ...]) $ O(k\log{N})+
値の削除 L.discard(x) $ O(\log{N})+
x not in L のときは何もしない
値の削除 L.remove(x) $ O(\log{N})+
x not in L のときは Error
pop L.pop(i=-1) $ O(\log{N})+
末尾以外の index を指定しても遅くならない
二分探索 L.bisect_left(x) L.bisect_right(x) $ O(\log{N})+
index L.index(x, l=None, r=None) $ O(\log{N})+
[l:r] 内で x が最初に出てくる index を得る
x not in L[l:r] のときは Error
irange L.irange(minimum=None, maximum=None, inclusive=(True, True), reverse=False)
minimum 以上 maximum 以下の値を順に得るイテレータ
inclusiceは端の値を含めるか否か。(True, False) とすれば半開区間 $ [\min, \max) にできる
dictと同様に D[key] でアクセス、D[key] = val で値を設定・変更できる。
i 番目の値を得るのは D.peakitem(i) : $ O(\log{N})
その他は Sorted Set と同様。
参考文献