一回でわかりやすく書くのは難しいので、簡潔データ構造 LOUDS の解説（全12回、練習問題付き）というシリーズにまとめました。 (2014/01/26) 古い内容を削除しました。
情報系修士にもわかるLOUDS - アスペ日記
一回でわかりやすく書くのは難しいので、簡潔データ構造 LOUDS の解説（全12回、練習問題付き）というシリーズにまとめました。 (2014/01/26) 古い内容を削除しました。
An Implementation of Double-Array Trie
Contents What is Trie? What Does It Take to Implement a Trie? Tripple-Array Trie Double-Array Trie Suffix Compression Key Insertion Key Deletion Double-Array Pool Allocation An Implementation Download Other Implementations References What is Trie? Trie is a kind of digital search tree. (See [Knuth1972] for the detail of digital search tree.) [Fredkin1960] introduced the trie terminology, which is
SegmentTreeの練習として良さそうなやつ - tozangezan's diary
id:kyuridenamidaに便乗してSegmentTreeで出来る問題たちをここに挙げておきます。 「良さそうなやつ」とか書いていますが単にSegmentTreeで解いた問題たちを並べておくだけです。残念。(解けないけどSegmentTreeと聞いているものも入れてあります) BITでかけるものもあるので、そういう問題はどっちで解いても良いと思います(多分BITのほうが定数が小さいです) あと、多分SegmentTree(もしくはBIT)を使わなくても解ける問題が入っているかもしれませんが、それはしかたがないです。少なくとも僕はこれらの問題をSegmentTreeかBITで解いています。 PKU 1631 Bridging signals 1986 Distance Queries 2019 Cornfields 2104 K-th Number 2373 Dividing the
セグメント木 問題集 - hogloidのブログ
https://twitter.com/hogloid/status/284225774142251008 こんなことを言ったので 書きます 問題は、セグメント木を使う解法がおそらく楽で、セグメント木が問題の重要な部分で、JOIとかPCKでない問題、とします（JOIの問題とかみんな知ってる&解いてるだろうし） あと、明確に悪問と分かる問題は載せません。 解説が欲しい場合は、(一応僕は全部解いたので)僕になにか言ってくれると解説ページを開設すると思います。下のコメント欄とかにどうぞ。 記事を出してからも、ボチボチ更新していく予定です。 ☆の数は、主観的な難易度です。 書き終わって気づきましたがかなりグロイ問題ばかりなのでやばいですが頑張ってください 似たような記事 http://d.hatena.ne.jp/tozangezan/20111111/1320993464 (こっちのほうが、おそ
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
Introduction to Segment Tree - Lilliput Steps
こんにちは, kagamiz(@kagamiz) です! この記事は, Competitive Programming Advent Calendar Div2012 18日目の記事として書かれました. この記事では, ぼくが気に入っているデータ構造であるセグメント木について, 説明と問題演習・問題紹介を交えながら紹介していきたいと思います. RMQ(Range Minimum Query)を処理するセグメント木はわかるけど, そこから応用するのが難しい...という方向けに書いていきます. 説明の章の先頭には, 水色の★もしくは黄色の★をつけています. ★は「プログラミングコンテストチャレンジブック」などでも触れられている事項で, ★はそうでない事項を指します. 演習問題の先頭には★マークをつけていますが, ★は基本的な問題, ★はやや難しい問題として示しています. 概要についてですが,
問題 I : 乱択平衡二分探索木
東京大学プログラミングコンテスト 2011 問題 L : 𝐿 番目の数字 東京大学大学院情報理工学系研究科 秋葉 拓哉 2011/05/14 東京大学駒場キャンパス 問題概要 • 各ノードに数字が決まってるツリーがある • 以下のタイプのクエリを大量に処理: ある頂点 𝒗 から 𝒘 への経路上の数字で， 𝒍 番目に小さい物を求めよ 頂点番号 頂点 1 に決ま っている数字 例: 頂点 1 から頂点 6 への経路での，3 番目 → 2, 5, 8, 7 の 3 番目 → 7 が答え 問題を変形 • 頂点 1 を根にして，向き付きの木にする • 以下を効率的に計算できるか？ 頂点 𝒗 から根までで 𝒙 以下が何個あるか？ 例: 頂点 4 から根に 6 以下は何個あるか？ → 8, 5, 2 に 6 以下は何個あるか？ → 2 個 それができると？ • それができると，任意の 2 頂
僕のセグメントツリーの使い方 - kyuridenamidaのチラ裏
セグメントツリーは、"できるだけ大きい区間で取って誤魔化す"のも大切ですが、それに加えて"遅延評価"をかなり意識すればいろんな木が簡単に特に思考なしでかけるイメージがあります。ちなみにここから説明するセグメントツリーは少し弄るだけで色んな変形が出来るのですきですが、冗長なので定数倍遅いです。ごめんなさい。 #include using namespace std; #define N (117) // update(l,r,v) := [l,r]の区間に対してvを一様に足す. k,a,bは飾り struct NODE{ int sum;//更新された値. この値を参照する時は評価が完全に完了しているようにする. int lazy; //遅延されている値を保存している NODE(){ sum = lazy = 0; } }; NODE seg[2*N]; // inlineつけないと大変
RMQ, LCAいろいろ - komiyamの日記
こことか蟻本を参考にして、色々実装を試してみた。 RMQ まず、インターフェースをはっきりさせよう。とりあえずD言語で書くけど、そこまで言語依存な書き方はしていないのですぐにC++なりJavaなりに移せるはず。D言語とかコンテストでは大抵使えないし言語仕様がまた変わるかもしれないのでそのうち自分でC++に書き直すと思う。それと全部未検証なことに注意。簡単なケースでしか試してない。 追記 いくつかバグを発見したのでそのうち修正する //気分的にはこんな感じ。 class RangeMinimumQuery(T, alias less = "a < b"){ this(); //RMQをビルドする this(in T[] xs); build(in T[] xs); //半開区間 [from, to)において最小値を与えるindexを返す //複数ある場合はもっとも若いindexを返す int
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Google Code Archive - Long-term storage for Google Code Project Hosting.
http://wwwisg.cs.uni-magdeburg.de/ag/lehre/SS2009/GDS/slides/S11.pdf
Segment Tree - Codeforces