データ構造と問い合わせ

概要

累積和・差分と局所link更新から始め、heap・ordered setと単調stackで候補を保つ。単調stackからCartesian treeを構築し、Fenwick TreeとSegment Treeの区間集約を学ぶ。monoid要約の直後にLazy Segment Treeの区間作用を置き、その後に関数合成・Sparse Table・SWAG・canonical decomposition・Merge Sort Tree・implicit Segment Treeを比較してから、run分割による動的区間管理を扱う。bucketとMo、bit列とfingerprintを用途別に比較した後、過去の版と条件付き更新へ進む。最後のSegment Tree Beatsでは遅延作用と償却解析を組み合わせる。

更新可能な最小十分要約

問い合わせの答えを合成でき、更新で保てる十分な統計量を導く。

考え方

queryでは答えそのものを毎回計算せず、次の更新・問い合わせに十分な要約を保つ。prefix、局所link、候補集合、区間の積、過去の版など、変更の単位と必要な演算から表現を選ぶ。

成立条件と計算量

初期化・更新・queryの費用を別に数える。結合則、逆元、冪等性、更新作用の閉性は異なる条件である。機能の多い構造へ直行する前に、静的な前計算や端点更新だけで済むかを考える。

章の構成

項目は各章の読書順に並べています。親子関係は順序と独立しているため、階層を字下げで表さず、子Unitには「概念上の親」を示します。導入項目は関連手法の見取り図で、発展的なUnitは対象色を目安に後から戻って学べます。

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

導入対象の目安: 緑色(800–1199)。必要な操作と保持する情報を整理し、基本コンテナから区間構造へ進む入口。

対象色の読み方は本書の読み方を参照してください。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-chapter-query

習得する技能

  • 問い合わせに十分で、更新と合成で保てる要約を導ける。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

問い合わせに必要な要約と更新規則を見抜く視点を先に学び、目的に合うデータ構造の選択へつなげる。

このUnitでは扱わないもの

  • なし

根拠