配列に対するブロック分割データ構造とその応用
本稿では、配列ベースのデータ構造におけるブロック分割（Block Decomposition）の概念と、様々な問題への応用について解説します。ブロック分割は、配列を一定サイズの小ブロックに分割し、各ブロックに対して集約情報や遅延更新メカニズムを導入することで、区間操作や点操作の計算量をバランス良く最適化する手法です。
ブロック分割の基本
配列を長さ約 \\(B\\) のブ ...
9月18日 09:56 投稿
青染之心の解法：重軽分解とブロック分割法
解法1: 重軽分解によるアプローチ
オフライン処理可能な問題特性を利用し、操作履歴から木構造を構築する。各ノードの解は根からそのノードまでのアイテムを用いた完全ナップサック問題と等価である。
深さ優先探索(DFS)実行時、再帰スタックにナップサック状態を保持する。空間計算量を削減するため、重軽分解(Heavy-Light Decomposition)を適用する。具体的には:
各ノー ...
5月31日 09:21 投稿