2020年4月3日動的計画法動的計画法, , テーマ記事, 競プロ, モノイド, 結合則, 木DP, 部分木, 全方位木DP, 単位元

競技プログラミングでよく出題される木DPについての説明と、それを同じ計算量で全頂点について求められるように応用した全方位木DPについて解説します。

木DP基本的な考え方とイメージ

木DP とは、根を一つ固定した木について、以 ...

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

セグメント木とは

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

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