Pythonでmultiset
だいたいのことがheapqとの組み合わせでできる
O(logn)で要素の挿入
O(1)で最小値の取得
O(logN)で要素の挿入、削除
O(1)で要素の存在確認、最小値の取得
二分探索ができない
二分探索
事前にソートして良いならbisect
k番目の値は読むだけ。O(1)
「kを超える最初の場所」がright、「k以上の最初の場所」がleft
固定のk番目の値が欲しい→ heapq
値域のサイズD
二分探索 O(logD)
追加削除はO(logD)
座標圧縮でDを圧縮することが効果的
「k番目の値」も「kを超える最初の値」も両方できる
AVL木
「順序付き集合は平方分割が速い」らしい(未確認
SkipList
Related Pages
- →ambiguous_stagnation×曖昧な停滞×明確な対立×対立回避×broad_and_shallow_listening×ブロードリスニング×広聴×広くて浅い×協力の深さと広さのトレードオフ×civic_muscle×パレート改善×existing_vendor×どこへ行ったのかのトレーサビリティ×agency×主体性×出した声が結果に変わる回路×decidim×geoip×nuro光でシンガポールと誤認される×マイナンバーカード認証×政府の効率化×ideation×agile_doctrine×機会を発信なしで知ることはできない×ダブルダイヤモンド×jonathan_fox×ダイヤモンドサンドイッチ×acute×immune_response×ハイパーローカル×⿻_plurality_&_6pack.care×reverse_procurement×参加型アカウンタビリティ×茹でガエル×chronic×uncommon_ground×地方課題×慢性×シビック・カタリスト×manufactured_urgency×緊急性の創出×shared_urgency×anton_eklund+_2023×特定データで機能するのは一般データでより楽×sensemaker×openai/gpt-oss×再現可能でなければ正統性がない×クローズドなモデルにロックインされないようにする×モダリティ×不可知論的ツール×specific_individual_topics×entire_systemic_viewpoint×実装より理論×アジェンダ設定の権限を人々に開放する×d-agreeシステム×台湾詐欺防止法×詐欺犯罪危害防制條例×fchpa×dbrand×cortico×スピーチとリーチ×言論の自由×freedom_of_speech×stanford_online_deliberation_platform×deliberative_polling×habermas_machine×再現性×artificial_intelligence_in_deliberation:_the_ai_penalty_and_the_emergence_of_a_new_deliberative_divide×pvcアルゴリズム×defensive_technology×d/acc×防衛的な集約×デジタル民主主義2030_meetup_#3×leon_erichsen×qvは決定論的×collaborative_meeding×civic_mascle×返信ボタンがない×層化無作為抽出×sitra×kerrokantasi×digifinland×polis×voxit×borgerforslag×folketing×your_priorities×message_checker×cofacts×roost×uncommon_groundのプロパガンダ×metaculus×6-pack_of_care×効用×ケア×connections_between_indivisuals_as_first-class_objects×joan_tronto×symbioenesis×共生進化×エピステミック・セキュリティ×epistemic_security×policy_lab×nesta×bit×demos×私たちが共に何かを知ることができることに関する安全保障×変容型ファシリテーション×実装ではなく思想が大事×スーパーノート→
- →数え上げ×degwer×状態をまとめる×dpは全探索の高速化×arc059f×codefestival_2016_final_f×aoj2439×探索順の変更×大きい順に並べる×aoj2333×順列は挿入dp×bit_dp×区間は終点でソート×条件の言い換え×操作は多いが産物は少ない×agc013d×線形和への分解×演算順序の変更×ビット演算を桁ごとに分解×部分群×操作が可逆で全域→部分群×ラグランジュの定理×再帰的定義→dp×arc037d×桁dp×aoj0570×累積和×フェニック木×高速フーリエ変換×ntt×高速ゼータ変換×and_と_add_の畳み込み×二分累乗×agc013e×行列木定理×全域木の個数×lgv公式×非交叉経路の個数×小さい確率を無視する×二項係数の公式×経路数×45度回転×xとyにわける×カタラン数×包除原理×agc005d×約数系包除×arc064f→
- →オイラー路×グリッド上の幅優先探索×ハンガリアン法×二部グラフの最大マッチング×二重辺連結成分分解×二重頂点連結成分分解×全点対間最短路×単一始点最短路×強連結成分分解×彩色数×最大クリーク×最大流×最大独立集合×最小全域有向木×最小全域木×最小流量制限付き最大流×最小費用流×橋/関節点×bit×binary-trie×convex-hull-trick-add-monotone×li-chao-tree×link-cut木_部分木クエリ×link-cut木×ウェーブレット行列×スパーステーブル×スライド区間の昇順k個の和×セグメント木×トライ木×マージ可能ヒープ×列の平方分割×平衡二分探索木×永続配列×素集合データ構造×UnionFind×ローリングハッシュ×接尾辞配列×最長共通接頭辞×最長回文×回文×複数文字列検索×hl分解×全方位木dp×最小共通祖先×木の直径×木の重心分解×根付き木に変換×mod-pow×オイラーのφ関数×オイラーのφ関数テーブル×ベル数×ラグランジュ補間×二項係数×二項係数テーブル×任意mod畳み込み×分割数×分割数テーブル×商列挙×形式的冪級数×形式的べき級数×拡張ユークリッドの互除法×拡張ユークリッド互除法×第2種スターリング数×約数列挙×素因数分解×素数テーブル×素数判定×組合せ×行列演算×進数変換×階乗×離散対数問題×高速フーリエ変換×divide-and-conquer-optimization×monotone-minima×スライド最小値×一次元累積和×二次元累積和×個数制限付きナップサック×最大長方形×最適二分探索木×最長増加部分列×ダブリング×包除原理×燃やす埋める問題×燃やす埋める×牛ゲー×mo’s_algorithm×offline-dynamic-connectivity×座標圧縮×アルゴリズム→
- →座標圧縮×setはメモリ食い×numba×numbaに複雑な型を渡す×numba bisect×numpy.unique×長方形グラフ探索×番兵×numba_np.concatenate×csr_matrix×リンクトリスト×mprof×atcoder→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]