2020年3月15日AtCoder座標圧縮,競プロ,セグメント木,区間,更新,データ構造,set,imos法,遅延評価セグメント木,イベントソート

問題へのリンク

問題概要

 N 回の通行止めがあり、 Q 人の人ははじめ座標 0 に立っている。 
\(i\) 番目の道路工事は時刻&n ...

2020年3月6日その他二次元区間和,区間和,テーマ記事,競プロ,区間,累積和,imos法

区間の更新がない場合

区間の更新が生じない場合は、累積和を用いることで高速にクエリを処理できます。

一次元の区間和

累積和を用いることで、

前処理：\(O(N)\)
クエリ：\(O(1)\)

で処理がで ...