取得:区間
NoviSteps2D
AtCoder
AtCoder550点
ABC-F
青色diff
【問題集】遅延評価セグメント木
遅延評価
遅延評価セグメント木
セグメント木
クエリ処理問題
データ構造
クエリ:区間更新
操作:区間
操作:加算
積の和に関する問題
取得:総和
数列
中堅以上の典型要素を詰め合わせた教育的問題
取得:区間
平方分割
数学(代数)
式変形
maspy さんの次のツイートがすべて!! F(cnt,sum) という組と定数加算作用が遅延セグ木にのるというのはよく知られていると思いますが、これは要素に対する (0乗和, 1乗和) と解釈できて、組 (0,1,...,k 乗和) などに一般化できます。今回は要素 (x,y) に対…
NoviSteps2Q
鉄則本
鉄則本A問題
鉄則本★4
AtCoder
累積和テク:左右両端からの累積和や累積結果を前処理
前処理
累積和
累積max
クエリ処理問題
N個のものうち1個を変更・削除したものを解く
取得:区間
取得:最大値・最小値
そのまま覚えたい典型問題
左右からの累積和・累積 max を前処理で求めておくのは、よくある典型!! 問題へのリンク 問題概要 個の整数からなる数列 が与えられる。次の 個のクエリに答えよ。 【クエリ】 区間 が与えられるので、数列からその区間を除外した領域について、整数値の最…
AtCoder
鉄則本A問題
そのまま覚えたい典型問題
セグメント木
クエリ処理問題
データ構造
RMQ
【問題集】セグメント木の入門
数列
鉄則本
NoviSteps1Q
鉄則本★5
取得:最大値・最小値
取得:区間
セグメント木の最初の練習問題によさそうな問題 問題へのリンク 問題概要 長さ の数列 がある。最初はすべての要素が 0 となっている。この数列に対して、以下の 2 種類のクエリに答えよ ( 個のクエリが与えられる)。 クエリ 1: が与えられるので、 の値を …