Shuz*'s Blog

事象の性質を考察する

区間係数付き加算・一点係数更新・一点和取得ができるデータ構造

はじめに

累積和高速化型貰うDPの添字に苦しめられたことはありませんか？私はあります。

なんと、貰う配る変換をしなくても、配るDPのまま高速化できるデータ構造があります。その名も Shuz* 木！（勝手に名付けた）

といっても非直感的なので係数セグ木と呼ぶことにします。

というわけで今回は係数セグ木の概要を書いていきます。

係数セグ木

概要

大きさ $2^n$ の配列と係数列に対し、区間係数付き加算・一点係数更新・一点和取得を $O(n)$ で行うデータ構造。

要件

$(M, +)$ はアーベル群
$R$ は環
$\times$ はスカラー乗法
$(M, +, R, \times)$ は左加群
$0 \in M$ は $M$ の $+$ の単位元
$-x \in M$ は $x \in M$ の逆元
$1 \in R$ は $R$ の $\times$ の単位元

インターフェース

$\rm initialize()$ : $a_0 \gets 0, a_1 \gets 0, \ldots, a_{{2^n-1}} \gets 0, b_0 \gets 1, b_1 \gets 1, \ldots, b_{{2^n-1}} \gets 1$
$\rm distribute(l, r, x)$ : $a_l \gets a_l + b_l \times x, a_{{l+1}} \gets a_{{l+1}} + b_{{l+1}} \times x, \ldots, a_{{r-1}} \gets a_{{r-1}} + b_{{r-1}} \times x$
$\rm update(x, y)$ : $a_x \gets b_x \times y$
$\rm get(x)$ : $a_x$ を返す。
$\rm change(x, y)$ : $b_x \gets y$

内部実装

らて木あるいは双対セグメント木を 1 つと、係数を保持する配列 1 つを持つ。係数が変更されるたびに和を取り出す。

実装例

終わりに

これで、ABC230-F も直感的に、バグらせずに書ける！うれしい！（解答例）