トライ木(Trie木) の解説と実装【接頭辞(prefix) を利用したデータ構造】
Trie木は、効率的な検索(retrieval)のために使われるデータ構造です。文字列などの先頭部分(接頭辞: prefix)の共通部分を共有して保存することで、\(O(M)\) での検索を可能にします。（文字列の長さを\(M\) と ...
Binary Indexed Tree (BIT) 総まとめ！区間加算や二次元BITまで
Binary Indexed Tree (またはフェニック木) は 数列 \(a_1, a_2, a_3, \cdots, a_n\) が与えられた時に、以下のようなことがそれぞれ \(O(log n)\) で実現できるデータ構造のこ ...
セグメント木を徹底解説！0から遅延評価やモノイドまで
セグメント木とは、完全二分木（全ての葉の深さが等しい木）によって実装された、区間を扱うのに適したデータ構造のことです。
区間に対する操作を対数時間 O(log n) で行えることが特徴で、競技プログラミング ...
Union-Find Tree を理解する！素集合系を扱うデータ構造
2つの集合が共通する要素を持たない時に「互いに素」であると言い、このような集合の集まりを「素集合系」などと言います。
素集合系の例素集合系は、いくつかの木構造を用いることで管理することができます。1つの集合は1つの木を用い ...
セット(Set)・集合のデータ構造
Setとは、数学における集合をデータ構造として表したものです。順序はなく、変更可能で、重複した要素を持ちません。
要素の挿入・削除・検索を高速に行うことができる特徴があります。
プログラム例Pythonの例Py ...
キュー(Queue)・待ち行列のデータ構造
キューは待ち行列とも呼ばれます。最初に格納したデータが最初に出てくるような、線形なデータ構造をしていて、このような順序をFirst In First Out (FIFO)と言います。
例えると、レストランにできる行列と一緒 ...
スタック(Stack)のデータ構造
線形なデータ構造の１つです。データを格納する操作(push)と取り出す操作(pop)について、対象になるデータの順番が決められています。
スタックは、最後に格納したデータが最初に出てくるようなデータ構造をしてい ...
連結リスト(Linked List)のデータ構造
連結リストはノードと呼ばれるデータの塊が、複数繋がってできたデータ構造です。
1つのノードは、格納する値自体と、次のノードへのアドレスを保持します。先頭から各ノードを辿ることで、線形に連結リストを探索すること ...
データ構造とは何か
データ構造とは、「コンピューターがデータを効率的に扱うための方法や構造のこと」です。これには様々な種類があり、それぞれに特徴があります。
アルゴリズムの話をする際に必ずと言っても良いほど出てくるのがデータ構造 ...
配列(Array)のデータ構造
配列は、連続したメモリ領域にデータを格納するシンプルなデータ構造です。データにアクセスしたい時は、配列の先頭から見て何番目のデータを取り出したいか(index)を指定します。
プログラミングを学ぶときに、必ずと学ぶ ...