noshi91のメモ

データ構造のある風景

データ構造

クエリが整数の Convex Hull Trick の 凸 判定

概要 Convex Hull Trick で最小値取得クエリの が整数の時、アルゴリズム内で直線が不要かどうかチェックする部分を簡単に記述することが出来る。 特に、傾きと切片を掛けることでオーバーフローする問題を発生させない。 本文 Convex Hull Trick で、最小値…

Range Mode Query 空間 Θ(n) 構築 Θ(n√n) クエリ Θ(√n)

概要 Range Mode Query - data-structures これをもう少しだけ詳しめに解説します。 面白いので好きなアルゴリズムです。 アルゴリズム まずは平方分割して、ブロックの境界を端点とする区間 ( 個ある) の全てについて最頻値とその頻度を計算します。 他にも…

部分永続 Union Find Θ(log(log(n)))

概要 部分永続 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…

列の連結/全要素列挙をする永続データ構造

某に載せるほどか...? 載せることにしたらこっちは消えます 以下の操作を実現する永続データ構造が存在する 単一の要素 からなる列を作成する 時間/空間計算量 列 を連結した列を作成する 時間/空間計算量 列 の全要素を順に列挙する 時間計算量 アルゴリズ…

(計算量 k 倍) 上位 k 個を取得する Li Chao Tree

概要 Li Chao Tree で小さいほうから 個取得できる ただし取り出した 個の順番は保証されない 空間計算量 時間計算量 per query アルゴリズム 全てのノードは高々 個の直線を保持します。 元の Li Chao Tree と同様、クエリの点を覆うノードの直線だけでクエ…

スライド最小値を半群に一般化する

概要 以前記事を書いたのですが消したので別の場所にもう一度書きました。 今度はある程度まともな実装付きです (その分遅いですが)。 Sliding Window Aggregation - data-structures 計算量解析 Queue の場合 ポテンシャル関数を で定義します。 Deque の場…

区間代入/区間積 Θ(logN)/query

概要 遅延セグメント木は様々な区間操作が で可能です。 一方で、代入と積の組み合わせは累乗を計算する必要があり、そのままでは に悪化してしまいます。 本稿では空間計算量を に抑えたまま、 で処理する手法を提案します。 また、積に限らず一般のモノイ…

2 ポインタ/ノード で親方向を探索する二分木

概要 最もシンプルなポインタによる二分木の実装は、各ノードが左子と右子を保持することでしょう。 一方でこの実装では親方向へ遡ることが出来ません。すると例えば平衡二分探索木のイテレータを実装するときなどに問題になります。 親へのポインタを保持す…

top tree 概要

概要 niuez.hatenablog.com top tree の記事が出ていたので、あまり触れられていない部分を補足していくモチベーションで書きました。 segment tree を知らないと読んでもあまり面白くないと思います。 link cut tree を知っていれば分かりやすいです。 その…

素集合の要素の列挙と併合 (単方向循環リスト)

概要 以下の 2 種類のクエリを処理します。 と同じ集合の要素を全て列挙します。 時間計算量 を含む集合の要素数 がそれぞれ含まれる集合同士を併合します。 が同じ集合に含まれているとバグりますが検出はできません。 時間計算量 理論 同一集合内のノード…

あなたの庭に永続データ構造を飾りませんか?

2019/02/06 永続 Stack のやや丁寧な実装例を追加しました 2020/12/13 数式などを整えました 概要 あなたのライブラリに新しい彩りを与える永続データ構造の紹介です。 永続データ構造とは 永続データ構造とは、普段のデータ構造で更新をするときに更新前の…

Splay Tree で三分探索木を組む

はじめに 最近競技プログラマーの間で Splay Tree のブームが来ているらしいので、それに乗っかり記事を書くことにしました。 Splay Tree は直近にアクセスした値への再アクセスが高速であったり、自己組織化する動的木にも使用されていたりと大変興味深い平…

構築 O(N) クエリ O(1) の RMQ

2019/03/10 大雑把な説明を追加しました 2019/07/08 細微な修正を行いました 概要 RMQ は競プロでも頻出のデータ構造です。本記事では競プロで実際に速度の向上が見込める高速な RMQ の実装について書きます。 本題 一般に良く知られる LCA に変換して ±RMQ …

WaveletMatrix で快適な整数列ライフを送ろう

この記事は内容に様々な問題があったので、削除されました。 Wavelet Matrix については下記のページを参照してください。 Wavelet Matrix - data-structures

UnionFindTree に関する知見の諸々

2018/08/17 ポテンシャル付きUnionFindTreeの記述を変更し、RetroactiveUnionFind についての記述を追加しました。 2019/07/19 集合内の要素の列挙についての記述を追加しました。 はじめに UnionFindTree って知ってますか? 競プロでは恐らく最も使用頻度…

Disjoint Sparse Table と セグ木に関するポエム

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とした…

各操作とmergeをO(α(N))で行うhashmap

概要 一般的なhashmapのサポートするキーの検索と挿入/削除に加えて、2つのhashmapを併合して1つにする操作を全てO(α(N))で行うhashmapの解説です。(α()はアッカーマン関数の逆関数) 注意点として、併合する可能性のあるhashmapにおいてkeyの重複は許され…

部分永続Union-Find Treeについて

スライドです(説明終了) バグってる可能性があるので注意してください verifyしましたが直したかどうか忘れました(最悪)