Writing a storage engine in Rust: Writing a persistent BTree (Part 1)
As part of a recent personal journey to better understand databases and better learn Rust, I have recently took on the project of writing a simple key-value storage engine. Crazy, right? Lets get started! B-Trees vs LSM TreesThe first thing one must think of when writing a key-value storage engine is -”How should I store my data so that I can perform reads and writes efficiently?”; The two most co
atcoder::lazy_segtree に1行書き足すだけの抽象化 Segment Tree Beats - ひとなので
AtCoder Library (ACL) の atcoder::lazy_segtree をもとにした Segment tree beats の抽象化の方法と，そのいくつかの具体的な使用例を紹介します．Segment tree beats は列に対する複雑な更新・取得処理を高速かつオンラインに実現する強力な手法ですが，実装の際に考慮すべきことが複雑でコーディング量も多く，体系立った実装方法の知見も整理されていないと筆者は認識しています．そこで本稿では，ドキュメントを含め極めて整備された ACL のコードをわずかに変更して Segment tree beats として使用する方法を紹介します．この方法では，様々な Segment tree beats の実装の大部分が共通化され，個別の問題に応じた機能は atcoder::lazy_segtree の利用時と同様にクラスや関数として組み込ま
Segment Tree のお勉強(2) | maspyのHP
遅延伝搬 Segment 木まで一通り、 $0$ から実装できるようことを目指して、丁寧に自習しました。折角なので記事化。 概要 前回 → Segment Tree のお勉強 (1) を前提としています。 1点更新、区間作用、区間積取得が可能な Segment 木。いわゆる非再帰実装 1-based index$N=2^n$ を仮定しない モノイド $A$ がモノイド $X$ に右作用するとします。各々のモノイドの二項演算を、積の形で、$$\begin{align*}A\times A\longrightarrow A;\quad (a,b)\mapsto ab,\\X\times X\longrightarrow X;\quad (x,y)\mapsto xy\end{align*}$$ と書きます。作用は、$$X\times A\longrightarrow X;\quad (x,a)
【全方位木DP】明日使える便利な木構造のアルゴリズム - Qiita
この記事について この記事では、一部で全方位木DP、Rerooting等と呼ばれているアルゴリズムの紹介/解説と、その実装についての簡単な説明を行います。 全方位木DPなどと物騒そうな名前がついていますが、発想自体は全く難しくありません。また、実装もそこまで難しいものではないです。 前提知識として、最低限のグラフ理論の知識(特に木構造について)を要求します。(有向木の根/部分木等…) 謝辞 この記事中に挿入されている図は、殆どを @259_Momone さんに提供して頂きました。素晴らしく美しい図を提供して頂き、この記事を分かりやすいものとして頂いたことに感謝いたします。 全方位木DPとは 各点から深さ優先探索を行って解くことができる問題のうち特定の条件(後述)を満たすものについて、全頂点についての答えを同等の計算量で求めることができるアルゴリズムです。 まず、全方位木DPで解くことができ
LCAをベースに構築するAuxiliary Treeのメモ - 日々ｄｒｄｒする人のメモ
(2019/09/15 20:50頃追記) ただAuxiliary Treeと書くと(一般的すぎて)齟齬を生む可能性が高いので、タイトル及び一部文章を変更しました。申し訳ないです。今回はLCAをベースに構築するAuxiliary Treeについて取り上げてます。 最近、LCAを元に構築する Auxiliary Tree を使う問題に出会ったので書いた。 CodeChef July Challenge 2019 で以下の問題があった。 smijake3.hatenablog.com 自分は Auxiliary Tree を使わず解いたが、想定解法が Binarization of a tree + Centroid Decomposition on Edge + Auxiliary Tree だったらしい。 discuss.codechef.com 以下を参考にしている。 虚树学习笔记 -
B-treeインデックス入門 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? B-treeがMySQLで使用されている背景から、B-treeインデックスの構造、そしてそれに基づいたインデックスの使用方法の入門編です。以下の流れに沿ってまとめていきます。 インデックスってなに？ B-treeってなんでインデックスに使われているの？ B-treeインデックスの構造 インデックスの使用方法 ※ 勉強をかねてまとめていることもあり、間違っている箇所がございましたら教えていただけると嬉しいです。 インデックスってなに？ 全体の内容の中から特定部分を探すために使用する、本の索引のような概念のことです。これを用いることで、検索
根付き木のハッシュ - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
りんごさん方式の記事 正当性を証明するにはユニークな多項式の形にしてmodを素数にしておけば、Schwartz–Zippel lemmaを使えて良いっぽい？ multisetのハッシュ、0になりやすいなぁと思ったけど0になる確率がat most n/modなのか。 記事での根付き木のハッシュの取り方を日本語にまとめておきます。 根付き木のハッシュ まず、深さ i に対応する乱数 を [0,mod) から取っておきます。 深さ i の頂点 v について、v 以下の部分木のハッシュは「( + 子のハッシュ)の積」として計算します。 特に、葉のハッシュ値は 1 です。 詳細は実際に記事を読んで下さい。 僕は根付き木のハッシュをどのように取っていたかの話と、それは良くなかったという話と、ならどうすれば良かったかの話をします。 計算法 まず素数p,modを用意する。 ある頂点以下の部分木ハッシュ値は
hoge木 - けんちょんの競プロ精進記録
Qiita に移植しました 重みつき Union-Find 木とそれが使える問題のまとめ、および、牛ゲーについて
遅延評価セグメント木をソラで書きたいあなたに - hogecoder
最下段が N-1 から始まるのと、親と子の取得方法がわかってればセグ木は書けます (ホンマか？)— 009_tsutaj@CODE FESTIVAL (@_TTJR_) 2017年3月29日 この記事は前記事: 「セグメント木をソラで書きたいあなたに」の続編です。セグ木をソラで実装するのはまだ厳しい・・・という方はまずはこちらの記事を読んでみてください。 tsutaj.hatenablog.com この記事は「セグメント木はソラで書けるけど、遅延評価セグ木は書けない・・・」という人を対象にしています。 遅延評価って何？ まず遅延評価について軽く説明しておきます。 遅延評価というのは、値の伝播*1を遅らせるテクニックです。これは区間に対して更新を行うときに必要になる時が多いです。例えば、値の更新を普通のセグメント木でやろうとしたとき、範囲の長さを とするとこの範囲の長さだけクエリを呼ばなけれ
フィボナッチヒープ - 宇宙ツイッタラーXの憂鬱
adventar.org フィボナッチヒープとは この記事ではヒープは最小値を求めるものとします。 フィボナッチヒープとは、フィボナッチ数の性質をうまく使ってならし計算量で高い性能を持ったヒープです。 ヒープ フィボナッチヒープ 二分ヒープ 最小値の削除 ならし O(log n) O(log n) 値の追加 O(1) O(log n) 値の追加が非常に多く、最小値の削除が非常に少ない場合は、二分ヒープより速くなることもあるかもしれません。他にもヒープ同士をマージできたり、ヒープ内の値の減少ができたりしますが、この記事では扱いません。すみません。 構造 図は wikipedia からの引用です。 フィボナッチヒープは、下図のようにいくつかのツリーを並べたような構造を持っています。ツリーの各ノードに、ヒープ内の値が入っています。各ツリーでは、上の根に近いほうが小さい値になるようになっています。
遅延伝播セグメント木について（旧：遅延評価セグメント木について） - beet's soil
もう12月まじ？こわれる はじめに 先にこっちを見て beet-aizu.hatenablog.com 2019/05/06 編集 遅延評価を遅延伝播に変更 問題例へのリンク↓を追加 beet-aizu.hatenablog.com 【はじめに】 これの続きです。 beet-aizu.hatenablog.com 前提としてうし木（普通のセグメント木）までは理解しているものとします。 この記事では後述する の場合だけ取り上げましたがそうでない例が↓の後半にあります。 beet-aizu.hatenablog.com 【遅延伝播セグメント木とは】 ある列に対して連続する区間に対して更新と取得ができるデータ構造である。以降遅延セグ木と略す。 前回のブログでは、要素の集合 と写像 からなるモノイド を考えた。 遅延セグ木では、新たに作用素の集合 と写像 からなるモノイド を追加し、 さらに作用と
セグメント木をソラで書きたいあなたに - hogecoder
セグ木がソラで書けなかったらセグ木に何か生やす問題とか解けない— つたじろう@帰省 (@_TTJR_) March 29, 2017 セグ木にいろいろ生やす問題がてんで解けない私なので、セグ木に慣れようと思い立ちました。そのためにはまずセグ木をもっと知らねばならないと思ったので、ソラで書けないか色々やっていました。 やってくうちにコツを掴んでソラで書けるようになってきたので、忘れないためにも記事を書くことにしました。ということで、何も見ずにセグ木を書くために押さえておきたいポイントを紹介していきます。 注意 この記事は、「セグ木がどんな形をしているかはわかるけど、実装はできない・・・」という方向けで、遅延評価が不要な、区間最小の基本的なセグメント木のみ扱っています。 そもそもセグ木って何という人は他記事を参考にしてください。 おすすめは iwiwi さんのスライド → プログラミングコンテ
子から異なる2つを選ぶ感じの木DPを解くアレ - よすぽの日記
子から異なる2つを選ぶ感じの木DPを解くアレを解くテクニックを紹介します。 D: Longest Path - Indeedなう（オープンコンテスト） | AtCoder とかが簡単に解けたりします 頂点0を根とする根付き木について 頂点iはa[i]を持つ(a[i] >= 0) 頂点iそれぞれについて、b[i] = a[i] + max(0, max(b[x] ただしxはiの子), max(b[x] + b[y] ただしx, yはどちらもiの子でかつx != y)) b[0]を求めよ という問題を考えます つまり、b[i]は子供から0, 1, 2個選んだ時のb[選んだ頂点]のsumのmaxにa[i]を足したものですね vector<int> g[MAX_V]; //g[p]は頂点pの子供を入れたvectorとする int a[MAX_V], b[MAX_V]; void dfs(int p
競技プログラミングにおける全方位木DP問題まとめ - はまやんはまやんはまやん
全方位木DP よく分かる解説 問題 CSA Connected Tree Subgraphs [解説 CF397 Tree Folding CF405 Bear and Tree Jumps AtCoder Driving on a Tree CSA Root Change EDPC Subtree 解説 CF Centroids 解説1 解説2 解説3 CF395 Timofey and a flat tree CF302 Road Improvement 解説 yukicoder No.768 Tapris and Noel play the game on Treeone 解説 違うけど方針が似ている問題 CF Nearest Leaf
CS Academy: Connected Tree Subgraphs - pekempey's blog
問題ページ modified 2018年12月21日 map を使ったこれはあやまりですので、キをつけてください。 modified 2018年12月17日 map を使うと書きやすいらしい。たとえば height を求めるには次のように書けばよい。 map<int, int> dp[100000]; vector<int> g[100000]; void dfs(int u, int p) { if (dp[u].count(p)) return; dp[u][p] = 0; for (int v : g[u]) if (v != p) { dfs(v, u); dp[u][p] = max(dp[u][p], dp[v][u] + 1); } } 解法 $O(n^2)$ 解法は TDPC の木という問題と同じ。 dp[v]:=vの部分木の番号の振り方を計算する。子が a,b,c,d だ
Aho Corasick 法 - naoyaのはてなダイアリー
適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと
Segment Trees
Motivational Problems: http://www.spoj.pl/problems/BRCKTS/ http://www.spoj.com/problems/GSS3/ http://www.spoj.com/problems/HORRIBLE http://www.spoj.pl/problems/IOPC1207/ https://www.spoj.com/problems/GSS2/ http://www.spoj.com/problems/SEGSQRSS/ http://www.spoj.com/problems/ORDERSET/ http://www.spoj.com/problems/HELPR2D2/ http://www.spoj.com/problems/TEMPLEQ Segment trees (shortened as segtrees), a
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Rubias19 porno gratis
VP trees: A data structure for finding stuff fast
The Unhealthy Obsession with Tree Questions