難易度目安：6 分野：データ構造 Discord（質問・議論） ▶ YouTube で解説動画を見る ↗ 1. 概要 数列や文字列などに対して，「区間 $[L,R)$ に含まれる要素の総和を求める」「区間 $[L,R)$ に含まれる最小値を求める」といった，区間クエリを処理する問題は…

難易度目安：6 分野：その他，未分類 Discord（質問・議論） 1. 概要 本講座では，競技プログラミング（あるいは AtCoder Algorithm Lectures）での使用頻度が高い，代数構造に関する用語および，その代表例について解説します． 代数構造は典型的には，集合…

難易度目安：4 分野：データ構造 Discord（質問・議論） 1. 概要 本講座では，静的な列に対する区間クエリを高速に処理するデータ構造である Disjoint Sparse Table （DST と略記することもあります）を解説します． Disjoint Sparse Table は，長さ $N$ の…

難易度目安：7 分野：データ構造 Discord（質問・議論） 1. 概要 通常のセグメント木は，更新を行うたびに古い状態を破棄し，常に最新のバージョンだけを保持する構造になっています．それに対して 永続セグメント木 は，過去のすべてのバージョンに対してア…

難易度目安：3 分野：データ構造 Discord（質問・議論） ▶ YouTube で解説動画を見る ↗ 1. 概要 本講座では，静的な配列に対するある種の区間クエリを高速に処理するデータ構造であるスパーステーブル（Sparse Table）を解説します． スパーステーブルは，事…

難易度目安：5 分野：データ構造 Discord（質問・議論） 1. 概要 本講座では，Sqrt Tree について解説します． Sqrt Tree は列の平方分割を再帰的に行うことでできる木構造です．特に静的なモノイド列に対する区間積クエリを高速に処理できます．具体的には…

難易度目安：7 分野：データ構造 Discord（質問・議論） 1. 概要 本講座では Sqrt Tree などに続き，再び静的なモノイド列に対する区間積クエリの問題を扱います． 特に，長さ $N$ の列について $\mathrm{O}(N)$ 時間の事前計算を前提とした場合，クエリあた…