【木マスター養成講座】4-1. Segment木ってなに〜？導入編【競プロかつっぱ】 - YouTube - Githubissues

hxrxchang / atcoder

https://atcoder.jp/users/hxrxchang

0 stars 0 forks source link

【木マスター養成講座】4-1. Segment木ってなに〜？導入編【競プロかつっぱ】 - YouTube #92

Open hxrxchang opened 3 months ago

hxrxchang commented 3 months ago

https://youtu.be/LjhVy1ZJTMc?si=iUWxKdHPWya0yytk

キーワード

セグメント木
セグ木

hxrxchang commented 3 months ago

セグ木でできること

区間の更新
区間の集約の取得

スクリーンショット 2024-07-16 13 29 19

hxrxchang commented 3 months ago

基本アイデア

完全2分木の葉に値を集約
各頂点に子孫の集約を保存
- ここでは最小値

スクリーンショット 2024-07-16 13 37 30

hxrxchang commented 3 months ago

1点の更新

例題: https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_bf

葉の値を更新するとき、親の頂点の更新は木なのでlogNで済む。

スクリーンショット 2024-07-16 13 40 39

hxrxchang commented 3 months ago

区間の更新

各頂点の更新が2logNで済む
- (区間の更新、取得が1点だったら遅延評価セグメント木は要らない。区間の更新、区間の取得には遅延セグ木が必要。)

スクリーンショット 2024-07-16 13 52 36

hxrxchang commented 3 months ago

https://www.youtube.com/watch?v=ReGvflPU81c

続き