2020年3月15日AtCoder競プロ, セグメント木, 区間, 更新, データ構造, set, imos法, 遅延評価セグメント木, イベントソート, 座標圧縮

問題へのリンク

問題概要

 N 回の通行止めがあり、 Q 人の人ははじめ座標 0 に立っている。 
\(i\) 番目の道路工事は時刻 \(S_i−0.5\) から時刻 \(T_i−0.5\) まで座標 \(X_i\) ...

2020年3月5日データ構造BIT, 区間和, 競プロ, 二分探索, セグメント木, 区間, データ構造, RAQ, RSQ, 転倒数, 二次元BIT

Binary Indexed Tree (またはフェニック木) は 数列 \(a_1, a_2, a_3, \cdots, a_n\) が与えられた時に、以下のようなことがそれぞれ \(O(log n)\) で実現できるデータ構造のこ ...

2020年2月27日データ構造二分探索, セグメント木, 二分木, 完全二分木, 区間, モノイド, 更新, RMQ, RUQ, データ構造, RAQ, RSQ

セグメント木とは

セグメント木とは、完全二分木(全ての葉の深さが等しい木)によって実装された、区間を扱うのに適したデータ構造のことです。

区間に対する操作を対数時間 O(log n) で行えることが特徴で、競技プログラミング ...

2020年1月18日データ構造競プロ, データ構造, 連結成分, Union-Find

2つの集合が共通する要素を持たない時に「互いに素」であると言い、このような集合の集まりを「素集合系」などと言います。

素集合系の例

素集合系は、いくつかの木構造を用いることで管理することができます。1つの集合は1つの木を用い ...

2019年11月30日グラフ入門, グラフ, 有向グラフ, データ構造, 無向グラフ, 重み付きグラフ, 用語・定義

グラフとは

頂点(ノード)と、頂点同士の関係を表したデータ構造です。

数学的には、グラフは以下の2つから構成されます。

頂点(ノード)の集合
頂点同士がつながっているか(隣接しているか)を表す、辺(エッジ)の集合 ...

2019年11月27日データ構造集合, データ構造, set

Setとは、数学における集合をデータ構造として表したものです。順序はなく、変更可能で、重複した要素を持ちません。

要素の挿入・削除・検索を高速に行うことができる特徴があります。

プログラム例Pythonの例

Py ...

2019年11月27日データ構造キュー, データ構造

キューは待ち行列とも呼ばれます。最初に格納したデータが最初に出てくるような、線形なデータ構造をしていて、このような順序をFirst In First Out (FIFO)と言います。

例えると、レストランにできる行列と一緒 ...

2019年11月25日データ構造スタック, データ構造

スタックとは

線形なデータ構造の1つです。データを格納する操作(push)と取り出す操作(pop)について、対象になるデータの順番が決められています。

スタックは、最後に格納したデータが最初に出てくるようなデータ構造をしてい ...

2019年11月25日データ構造入門, データ構造, 連結リスト

連結リストとは

連結リストはノードと呼ばれるデータの塊が、複数繋がってできたデータ構造です。

1つのノードは、格納する値自体と、次のノードへのアドレスを保持します。先頭から各ノードを辿ることで、線形に連結リストを探索すること ...

2019年11月25日データ構造入門, データ構造

データ構造とは

データ構造とは、「コンピューターがデータを効率的に扱うための方法や構造のこと」です。これには様々な種類があり、それぞれに特徴があります。

アルゴリズムの話をする際に必ずと言っても良いほど出てくるのがデータ構造 ...