考察
片方の配列へ同じ値を足したとき、積の増分はもう片方の配列の値に比例する。そこで、答えとなる積和に加えて両配列の和と区間長を持てば、区間内の要素を一つずつ見ずに更新できる。この四つを遅延セグメント木で管理する。
積和を更新するには何が足りないか
求めるのは、指定区間の各位置で二つの値を掛け、その結果を足した値である。区間内を毎回走査すると、最悪で 時間かかる。 なので、区間全体への加算と積和の取得を高速に行いたい。
まず、 の各要素に を加える操作だけを考える。一つの位置 では、積の変化は次のように書ける。
従って、更新区間全体での積和の増分は、その区間の の和を 倍したものになる。積和だけを保存しても更新できず、もう片方の配列の和が必要である。対称に、 への加算には区間の の和が必要になる。
では、追加した二つの和自身はどう更新すればよいか。長さ の区間で の各要素に を加えれば、 の和は 増える。 の和も同様なので、区間長も持てば、必要な情報をすべて更新できる。
ここで、区間 の要約を次の四つ組で定義する。
- :区間長。
- : の区間和。
- : の区間和。
- :答えに使う積和。
実装上の名前では、順に len、sumA、sumB、sumAB に対応する。以下の和と積はすべて を法として計算する。加算・乗算だけで各式が成り立つので、途中でも余りを取ってよい。
二種類の加算を一つの操作で表す
遅延セグメント木では、子へまだ伝えていない操作をまとめて保存したい。そこで、 に 、 に を加える操作を、加算量の組 で表す。種類1のクエリは 、種類2で を加えるクエリは である。
一つの位置で両方を加算した後の積を展開する。
これを区間全体で足すと、最後の は要素数だけ現れる。従って更新後の積和は次の値になる。
元のクエリは片方への加算だが、遅延させた操作をまとめると の両方が非零になる。その合成後の操作にも対応するため、 を省いてはいけない。 要約全体への作用は、次の三式と、長さが変わらないことで定まる。
右辺の はすべて、この操作を適用する直前の値である。実装では先に古い sumA、sumB から新しい sumAB を計算し、その後に二つの和を更新するか、更新前の要約から新しい要約を別に作る。この変換を mapping(f, S) と呼ぶ。
二つの操作 、 をこの順に行うと、各要素への加算量は足し合わされる。
この合成を composition(f2, f1) とする。恒等作用、すなわち何もしない操作は である。保存する遅延タグはこの加算量の組だけでよく、積和の増分をタグへ別に保存する必要はない。
二要素で更新前の和と合成を確かめる
独自の小例として、区間全体で 、 とする。初期要約は である。この区間の に2を加え、続いて に5を加える。
一回目は 、二回目は となる。二回目に使う は、二回目の操作の直前の和である。一回目の更新より前の ではない。
一方、タグをまとめれば と の合成は となる。初期要約へ一度に作用させると、今度は初期の を使い、積和は次の値になる。
更新後は なので、要素ごとの計算 とも一致する。合成後の作用で交差項 が補うのは、先の 加算によって増えた部分へ、後の 加算が作用する分である。逆順に処理しても、積和は 、続いて と同じになる。この加算同士は順序を交換できるが、各回の式にはその回の更新前の和を使う。
要約を木に載せてクエリを処理する
隣接する左右区間の要約は、四成分をそれぞれ足せば結合できる。この結合を op とする。積和は同じ位置どうしの積を足したものなので、左右をまたぐ積を追加する必要はない。空区間の要約は である。
- 位置 の葉を とし、下から
op で結合して木を構築する。各ノードの遅延タグは で初期化する。
- 区間全体を更新するときは、ノードの要約へ
mapping を適用し、既存タグの後に新しい操作を合成する。子へ降りる必要が生じるまでは、子への反映を保留する。
- 更新または照会が区間の一部だけにかかるなら、保留中のタグを左右の子へ適用して親のタグを恒等作用へ戻し、必要な子へ降りる。部分更新から戻ったら左右の要約を結合し直す。
- 積和の照会では、指定区間を覆うノードの要約を結合し、その を出力する。交わらない区間からは を返す。
AtCoder Library を使うなら、種類1・2は apply にそれぞれ ・ を渡し、種類3は prod の結果の積和を読む。要約・作用・合成はいずれも定数サイズなので、各クエリを 時間で処理できる。
典型の発動条件
積のrange updateに必要なmoment拡張
区間の答えだけでは一括更新できないとき、一要素での変化を展開し、総和を取って不足する量を探す。さらに、その補助量自身の更新に何が必要かも確認する。本問では積和から二つの一次の和、そこから長さを追加すると、それ以上の情報が不要になる。
遅延segment treeの作用設計
区間を結合できるだけでなく、一括更新を要約だけから計算でき、複数の更新も同じ形式にまとめられるときに候補になる。要約の結合、恒等作用、合成順、左右に更新してから結合しても結果が変わらないことを確認する。
問題固有の要素
同じ位置の二配列の積を問うため、 への加算の係数には の和が、 への加算の係数には の和が現れる。元のクエリが片方だけへの加算でも、操作をまとめた表現では両方への加算を扱う。この違いに注目すると、交差項 の必要性を見落としにくい。
正当性
区間の要約は、その区間に含まれる要素数と三種類の総和を表す。左右区間が重ならなければ各成分の和が全体の要約になり、成分ごとの加算は結合的である。空要約 を結合しても値は変わらない。従って、区間をどのように分割して結合しても、同じ要約を得る。
mapping は一要素の積の展開を総和した式なので、その区間へ加算した後の要約を正確に返す。長さと三つの和はすべて左右の和であり、更新後の各成分もそれらの線形結合である。よって、左右を結合してから同じ操作を適用する結果と、左右へ適用してから結合する結果は一致する。空要約にはすべての成分が0のまま作用し、恒等作用 はどの要約も変えない。
二つの操作を順に適用することは、各要素へ加算量の成分和を一度に加えることと等しい。mapping が各要素への操作を正確に要約するので、タグを composition でまとめても要約は一致する。従って、子への更新を保留しても、子へ降りる前に合成タグを伝播すれば、一回ずつ更新した場合と同じ要約が得られる。
葉の初期値は定義どおりであり、結合・全体更新・タグの伝播・部分更新後の再結合はいずれもこの意味を保つ。照会区間を重複なく分割して結合した要約の は、現在の配列の指定区間における積和そのものである。以上は加算・乗算の等式だけを用いるため、法上で計算した値も要求された余りに一致する。
実装上の注意
mapping の右辺はすべて更新前の値から評価する。sumAB を計算し終えてから sumA、sumB を書き換える。
- 入力の1始まり閉区間 は、0始まり半開区間を使う実装では にそろえる。長さ1や全区間も同じ規則で扱う。
- 初期値・加算量を法で正規化し、積の途中でも余りを取る。各因子を法未満にしても、 を剰余なしで一度に掛けると64 bit整数に収まらない。剰余整数型を使うか、二因子ずつ十分な幅で掛けて剰余を取る。
復習の核
- 区間の答えを一括更新できなければ、一要素の変化を展開してから総和を取り、必要な補助量を洗い出す。その補助量自身も更新できるか確かめる。
- 元のクエリだけでなく、複数クエリを合成した操作にも更新式が対応しているか確認する。
- 二回の作用と合成後の一回の作用を小例で比べる。「更新前」は、適用する操作ごとの直前を指す。
計算量と制約
時間
葉の初期化と木の構築に 時間、各クエリに 時間かかる。全体で 時間。
空間
個のノードに四成分の要約と二成分の遅延タグを保存する。入力配列と木を合わせて 空間。
制約との対応
に対し、各クエリでは対数個のノードを処理する。初期値は 、加算量は だが、答えは で割った余りなので、配列の実際の値を蓄積せず法上の要約とタグを保持すればよい。 で入力の照会区間は空でないが、木の内部で使う空要約も上記の規則で処理できる。
出典