フェニック木
部分和の計算と要素の更新の両方を効率的に行える木構造
BITと略される
>保坂 和宏 (東京大学理学部数学科)
> 第 13 回 JOI 春合宿
> 2014/03/19
k 番目の値を高速に取り出せるデータ構造として使うことができる
集合への追加削除とkth取得
素朴な方法としては値域のサイズDの配列を用意して、値のあるところに1を立てる
インクリメントに変えれば同じ値が複数個あるケースにも対応できる(multiset)
O(1)で追加削除可能
kthの取得は端から数えていくので遅い
これをBITにする
BITは部分和がO(logD)
これに対して二分探索すれば良い
工夫するとO(logD) see 保坂さんの資料
ただし追加削除はO(logD)
座標圧縮でDを圧縮することが効果的
集合の中である値の次の値が知りたい時
まずその値までの和を取って、1加えて二分探索
これを繰り返せば「ある値より大きいものの取得」もできる
pythonN = 1000
bit = [0] * (N + 1) # 1-origin
def bit_add(pos, val):
x = pos
while x <= N:
bit[x] += val
x += x & -x # (x & -x) = rightmost 1 = block width
def bit_sum(pos):
ret = 0
x = pos
while x > 0:
ret += bit[x]
x -= x & -x
return ret
def bit_bisect(lower):
"find a s.t. v1 + v2 + ... + va >= lower"
x = 0
k = 1 << (N.bit_length() - 1) # largest 2^m <= N
while k > 0:
if (x + k <= N and bit[x + k] < lower):
lower -= bit[x + k]
x += k
k //= 2
return x + 1
bit_add(12, 1)
bit_add(34, 1)
bit_add(56, 1)
print(bit_sum(20)) # => 1
print(bit_sum(40)) # => 2
print(bit_sum(60)) # => 3
print(bit_bisect(2)) # => 34Related 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×私たちが共に何かを知ることができることに関する安全保障×変容型ファシリテーション×実装ではなく思想が大事×スーパーノート→
- →オイラー路×グリッド上の幅優先探索×ハンガリアン法×二部グラフの最大マッチング×二重辺連結成分分解×二重頂点連結成分分解×全点対間最短路×単一始点最短路×強連結成分分解×彩色数×最大クリーク×最大流×最大独立集合×最小全域有向木×最小全域木×最小流量制限付き最大流×最小費用流×橋/関節点×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×座標圧縮×アルゴリズム→
- →二分ヒープ×データ構造×ヒープキュー×優先度キュー×priority_queue×ある集合に値が追加削除される。最小の値を取得したい。×m個の数がn個の集合を移動する。集合の最小要素を得たい×n個の値が更新される、最小値を知りたい×ヒープのk番目の値を更新したい×中央値×best_kの取得→
"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]