データ構造とアルゴリズム - Qiita Advent Calendar 2019 - Qiita
データ構造とアルゴリズムに関する話題なら何でもOKです。 メジャーなものからマイナーなものまで様々なトピックを好きなように書きましょう！ カレンダーの愛称は「デーアルアドカレ」でお願いします！ 関連： 以下は「文字列アルゴリズム Advent Calendar」を含みますが、実態は何でもありで様々なデータ構造とアルゴリズムが紹介されています。 文字列アルゴリズム Advent Calendar 2016 - Qiita 文字列アルゴリズム Advent Calendar 2017 - Qiita データ構造とアルゴリズム Advent Calendar 2018 - Qiita データ構造とアルゴリズム #2 Advent Calendar 2018 - Qiita
CodeChef GPD Gotham PD - kazuma8128’s blog
問題文 https://www.codechef.com/problems/GPD 問題概要 頂点数 N の根付き木が与えられる. 各頂点には正整数のキーが付いている. 以下の二種類の Q 個のクエリをオンラインで処理せよ. クエリ１：頂点 v の子に, キー k の付いた新しい頂点 u を増やす クエリ２：頂点 v から根までのパスに含まれる頂点に付いたキーの中で, k でXORしたときの最大の値と最小の値を求める 制約：1 ≤ N ≤ 10^5, 1 ≤ Q ≤ 2*10^5, 1 ≤ (各キー) ≤ 2^31-1 解法 まず, トライ木を使うと, 要素の挿入 (insert) , 要素の削除 (erase) , ある値でXORしたときの最大値/最小値の取得が O(ビット数) でできます. 詳しくは以下のページなどを参照 www.geeksforgeeks.org これを使って根からD
非負整数値を扱う Trie について - kazuma8128’s blog
はじめに 非負整数を二分木のトライ木で管理するアレに関する日本語記事があんまり無いっぽいので雑にメモ. （というかそもそも専用の呼び名ないのかな？） とりあえずここでは Binary Trie って呼んどきます. Binary Trie とは 整数をビット列とみなしてトライ木っぽく持つ set 的なことができるデータ構造です. 正確には要素の重複を許す multiset っぽく実装することが多そう. 整数集合を管理できますが, 平衡二分木よりも実装が楽なので最高です. こんな感じ ノードに書いてある数字は部分木に含まれる要素の個数です. できること ビット長を B とすると, 以下の操作が全て O(B) でできます. insert(x) : 値 x を集合に（一つ）追加 erase(x) : 値 x を集合から（一つ）削除 max_element/min_elemet() : 集合内の最大
『みんなのデータ構造』発売および予約開始のお知らせ – 技術書出版と販売のラムダノート
ご来店ありがとうございます。 本日より、新刊『みんなのデータ構造』の発売を開始しました。紙書籍の発送は7月25日前後を予定しています。電子書籍は購入後すぐにお読みいただけます。 『みんなのデータ構造』は、Pat Morin氏による “Open Data Structures” を翻訳して書籍として出版するものです。Pat Morin氏による原文は、クリエイティブコモンズ継承ライセンス（CC BY）で公開されており、誰でも自由に教材として活用できるだけでなく、内容に手を入れて別のライセンスで再配布したり、販売したりできるようにされています。堀江氏、陣内氏、田中氏による翻訳と、ラムダノート株式会社による編集も、すべてCC BYで公開しており、同様に自由に利用していただくことが可能です。 書籍版『みんなのデータ構造』（紙書籍および電子書籍）につきましては、クリエイティブコモンズライセンスではなく
Bloom Filters by Example
A Bloom filter is a data structure designed to tell you, rapidly and memory-efficiently, whether an element is present in a set. The price paid for this efficiency is that a Bloom filter is a probabilistic data structure: it tells us that the element either definitely is not in the set or may be in the set. The base data structure of a Bloom filter is a Bit Vector. Here's a small one we'll use to
Bloomフィルターについて調べた
Eric Redmond & Jim R. Wilson 著の”Seven Databases in Seven Weeks” を読んでいたところ、Ch.8 Redis の Day2 で書籍名の重複チェックに Bloom Filter という確率的データ構造(アルゴリズム?)が利用されていた。本ではさらっとしか触れられていなかったので調査。 処理の流れ 材料 ビット配列(m ビット) ハッシュ関数(k個。整数1からm のどれかをかえす) 作り方 下ごしらえ ビット配列の各ビットは予め0で初期化しておく。 各初期データをk個のハッシュ関数に食わせ、ハッシュ関数のかえすビットを立てる。 重複チェック 重複チェックしたい入力値をk個のハッシュ関数に食わせる ハッシュ関数のかえすビットがビット配列で立っているかチェック すべてのビットが立っていれば、重複と判定。 一つでも立っていないビットがあれば
Re永続データ構造が分からない人のためのスライド
Competitive Programming Advent Calendar 2012の12/01担当分の記事です。
競技プログラミングにおける永続データ構造問題まとめ - はまやんはまやんはまやん
永続データ構造 persistent data structures 解説 色々ある「永続配列」「永続セグメントツリー」「永続Union-Find」「永続木」「永続平衡二分木」「永続WaveletMatrix」参考 部分永続。最新版のみ変更可能、Undoができる機構がある。履歴は一直線。 完全永続。昔のどのバージョンからでも変更でき、履歴が全て残っている。履歴は木。 永続配列があれば永続Union-Findが作れるらしい 永続配列は永続木があれば作れるらしい 部分永続Union-Findの資料 部分永続はスタックで履歴を残しておいて逆操作をしていって戻すやり方がある（要出典）多分そのやり方でやってる 平衡二分木を永続化するときは赤黒木が最良らしい 問題 完全永続セグメントツリー SPOJ D-query CF429 Destiny (要素add,特殊クエリ) 部分永続セグメントツリー CS
C++でブルームフィルタを実装する方法 | POSTD
ブルームフィルタとは、「ある要素が集合のメンバである可能性があるか、それとも確実に集合のメンバではないか」を効果的に確認することのできるデータ構造です。この記事では、C++でブルームフィルタを実装する簡単な方法をご紹介します。 ブルームフィルタとは何なのか 、また、 その背後にある多くの数学的要素 については紹介していませんので、ご了承ください。これらのトピックに関しては、素晴らしいリソースがあるので、そちらを参考にしてください。 インターフェイス まずは、ブルームフィルタを定義していきましょう。ここでは、3つのパブリック関数を定義していきます。 コンストラクタ ブルームフィルタにアイテムを追加する関数 アイテムがブルームフィルタにある可能性を確認するためのクエリを行う関数 また、フィルタの状態を保持するビットの配列を含んだ、メンバ変数についても定義します。 #include <vecto
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Bloom filter
乱択アルゴリズム紹介(Bloom Filter) - Preferred Networks Research & Development