データ構造
昔の記事で Disjoint Sparse Table には半群が乗るという思想を言ったのですが、使う上ではモノイドにして空の区間に対応した方が嬉しいし、そもそも実装を変えると自然に長さ の区間に対応できることに気付きました。 お騒がせして申し訳ありません。 ACL …
概要 std::priority_queue (binary heap) を つ持って、片方には削除待ちの要素を入れることで、実質的に削除ができるようにするテクニックがある。 ただし、これは invalid な削除も可能になってしまう。 つまり、存在しない要素 を削除する操作をした後に …
概要 木上の等高線集約クエリ - suisen のブログ この記事で未解決になっていた変種 を解決する。 を可換モノイドとし、 頂点の木 の各頂点には の元が書き込まれているとする。 に書かれている値を に書き換える。 から距離 以上 未満の頂点に書かれた値の…
注意: 雑です 概要 [1] で定義された top tree は、葉が underlying tree の辺に対応するなどの条件があります。 [2] は splay tree をベースにした top tree を説明しています。 [1] の定義にはわずかに合致しないものの、いくらかの良い性質を持つ構造を思…
概要 Wavelet Matrix は 2 次元空間の点群に関するクエリを処理するデータ構造と見ることが出来ます。 これを発展させて 3 次元空間の点群に関するクエリを で処理するデータ構造が存在します。 出来ること を非負整数の つ組の列として、データ構造を構築す…
概要 Convex Hull Trick で最小値取得クエリの が整数の時、アルゴリズム内で直線が不要かどうかチェックする部分を簡単に記述することが出来る。 特に、傾きと切片を掛けることでオーバーフローする問題を発生させない。 本文 Convex Hull Trick で、最小値…
概要 Range Mode Query - data-structures これをもう少しだけ詳しめに解説します。 面白いので好きなアルゴリズムです。 アルゴリズム まずは平方分割して、ブロックの境界を端点とする区間 ( 個ある) の全てについて最頻値とその頻度を計算します。 他にも…
概要 部分永続 Union Find のアルゴリズムの変種を考えました 注意: 実測では使い物にならない気がします 空間計算量 - 単一の要素からなる集合 個で初期化する 時間計算量 - と が属する集合を併合する 時間計算量 - 回目に が呼ばれた直後に が属していた…
概要 SegmentTree などのように、代数的構造 (特にモノイド) を乗せるデータ構造は多い。 この部分の設計は様々だが、「静的メンバを実装した型を受け取る」設計を他の設計と比較する。 設計のバリエーション A: std::function で関数オブジェクトを持つ tem…
随時募集しています 略称 正称 APSP All Pairs Shortest Path BB Branch and bound BBST Balanced Binary Search Tree BFS Breadth First Search BIT Binary Indexed Tree BM Berlekamp-Massey BM Boyer-Moore BSGS Baby-Step Giant-Step CHT Convex Hull Tr…
某に載せるほどか...? 載せることにしたらこっちは消えます 以下の操作を実現する永続データ構造が存在する 単一の要素 からなる列を作成する 時間/空間計算量 列 を連結した列を作成する 時間/空間計算量 列 の全要素を順に列挙する 時間計算量 アルゴリズ…
概要 Li Chao Tree で小さいほうから 個取得できる ただし取り出した 個の順番は保証されない 空間計算量 時間計算量 per query アルゴリズム 全てのノードは高々 個の直線を保持します。 元の Li Chao Tree と同様、クエリの点を覆うノードの直線だけでクエ…
概要 以前記事を書いたのですが消したので別の場所にもう一度書きました。 今度はある程度まともな実装付きです (その分遅いですが)。 Sliding Window Aggregation - data-structures 計算量解析 Queue の場合 ポテンシャル関数を で定義します。 Deque の場…
概要 遅延セグメント木は様々な区間操作が で可能です。 一方で、代入と積の組み合わせは累乗を計算する必要があり、そのままでは に悪化してしまいます。 本稿では空間計算量を に抑えたまま、 で処理する手法を提案します。 また、積に限らず一般のモノイ…
概要 最もシンプルなポインタによる二分木の実装は、各ノードが左子と右子を保持することでしょう。 一方でこの実装では親方向へ遡ることが出来ません。すると例えば平衡二分探索木のイテレータを実装するときなどに問題になります。 親へのポインタを保持す…
概要 niuez.hatenablog.com top tree の記事が出ていたので、あまり触れられていない部分を補足していくモチベーションで書きました。 segment tree を知らないと読んでもあまり面白くないと思います。 link cut tree を知っていれば分かりやすいです。 その…
概要 以下の 2 種類のクエリを処理します。 と同じ集合の要素を全て列挙します。 時間計算量 を含む集合の要素数 がそれぞれ含まれる集合同士を併合します。 が同じ集合に含まれているとバグりますが検出はできません。 時間計算量 理論 同一集合内のノード…
2019/02/06 永続 Stack のやや丁寧な実装例を追加しました 2020/12/13 数式などを整えました 概要 あなたのライブラリに新しい彩りを与える永続データ構造の紹介です。 永続データ構造とは 永続データ構造とは、普段のデータ構造で更新をするときに更新前の…
はじめに 最近競技プログラマーの間で Splay Tree のブームが来ているらしいので、それに乗っかり記事を書くことにしました。 Splay Tree は直近にアクセスした値への再アクセスが高速であったり、自己組織化する動的木にも使用されていたりと大変興味深い平…
2019/03/10 大雑把な説明を追加しました 2019/07/08 細微な修正を行いました 概要 RMQ は競プロでも頻出のデータ構造です。本記事では競プロで実際に速度の向上が見込める高速な RMQ の実装について書きます。 本題 一般に良く知られる LCA に変換して ±RMQ …
この記事は内容に様々な問題があったので、削除されました。 Wavelet Matrix については下記のページを参照してください。 Wavelet Matrix - data-structures
2018/08/17 ポテンシャル付きUnionFindTreeの記述を変更し、RetroactiveUnionFind についての記述を追加しました。 2019/07/19 集合内の要素の列挙についての記述を追加しました。 はじめに UnionFindTree って知ってますか？ 競プロでは恐らく最も使用頻度…
2018/09/09 実装を少し変更しました 2021/02/18 数式を tex を使ったものに変更しました 2021/02/18 不適切な表現を変更しました 2021/02/18 msb の意味が適切でなかったので、修正しました 前半: https://discuss.codechef.com/questions/117696/tutorial-d…
はじめに JOIの春合宿で簡潔データ構造の講義があり、競プロ界隈でも簡潔データ構造の機運が高まっているため(本当か？)、競プロで便利なビットベクトルの実装について書きます。 本記事で紹介する実装では、以下の性能を実現します。 bit列の長さをNとした…
概要 一般的なhashmapのサポートするキーの検索と挿入/削除に加えて、２つのhashmapを併合して１つにする操作を全てO(α(N))で行うhashmapの解説です。(α()はアッカーマン関数の逆関数) 注意点として、併合する可能性のあるhashmapにおいてkeyの重複は許され…
スライドです(説明終了) バグってる可能性があるので注意してください verifyしましたが直したかどうか忘れました(最悪)
