えびちゃんの日記

えびちゃん（競プロ）の日記です。

区間平均値に関する典型の例

おつまみ記事

å°Žå…¥

配列 $a = (a_0, a_1, \dots, a_{n-1})$ に対して適当な区間 $[l\lldot r)$ が与えられて、そこでの平均値 $f_a(l, r) = \tfrac1{r-l}\sum_{i=l}^{r-1} a_i$ を考えます。

たとえば $[l\lldot r)$ がたくさん与えられて平均値を求めるだけなら、累積和を用いるだけでよいです。 あるいは $a_i$ を $x$ に更新するようなクエリがたくさん与えられる場合も、セグ木を用いるだけでよいです。

では、左端 $l$ を固定した場合に平均値を最大たらしめる右端 $\argmax_{r\gt l} f_a(l, r)$ を求めたい場合はどうしましょう。値の更新はないものとします。

本題

平均値の分子 $\sum_{i=l}^{r-1} a_i$ の方を累積和として扱うのは比較的自然に見えるでしょう。 分母の $r-l$ が厄介な気がします。

一旦累積和の形で書いてみます。 $$s_i = \sum_{j=0}^{i-1} s_j = a_0 + a_1 + \dots + a_{i-1}$$ とすると、該当の平均値は $\tfrac{s_r-s_l}{r-l}$ と書けます。

この式は、$(x_i, y_i) = (i, s_i)$ なる点たち ($i \in [0\lldot n]$) を考えたときの、点 $l$ と点 $r$ を結ぶ直線の傾きと見ることができます*1。

そこで、そういう点たちを考えます。 これ以降においては、もう元の $a_i$ のことは一旦忘れて $s_i$ だけを気にするだけで済みます。

元々求めたかったものは、点 $l$ より右にある点のうち、点 $l$ と結んだときに傾きが最大となる点の番号であるとわかります。 これは、平面走査などを行うことで各 $l$ に対して求めることができます。 凸包だと思う方が見通しがよいと感じる人もいるかもしれません？ いろいろな見方を身につけておく方がよさそうです。

例題

他にもいろいろ考えられるかも。

所感

geometry に帰着させるテクニック天才がち。 CHT で高速化する DP とかもそう。 矩形クエリとかに帰着させてセグ木で平面走査をしたり wavelet matrix を使ったりするのも似たジャンルではありそう。 とはいえセグ木がセグ木以外全部より典型感ある気がする。

geometry のいろいろなことをちゃんとやる前提だと、当然のように永続赤黒木とかが出てきて大変そうなので AtCoder では出なさそう (cf. CS166.1226/18)*2。

区間の長さ・要素数を扱いたいときに $1$ をどこかしらに登場させるテクかしこい。 ABC 146 E もそういう気配を感じる。

個数を $0$ 乗和と見るのは $k$ 乗和を求める DP で出てきがち。 遅延セグ木で区間加算・区間和を求めるときにも $0$ 乗和と $1$ 乗和のペアを持っているという解釈が自然*3。

もちろん、「区間平均値といえば絶対これ」で思考停止するのはよくなさそう。処理したいクエリに応じて適切な考察をする必要があるので。

近況

最近はいわゆる merge/split のできる B-tree を書こうとしています。merge じゃなくて concat とか append とか呼びたい気持ちはあります。merge は一般的な名称すぎてくっつけ方の情報が薄いので。

だんだん unsafe Rust や Stacked/Tree Borrows とも仲よしになってきた感じがあります。 unsafe 由来の UB ではなくシンプルに添字の off-by-one などで木がグチャグチャになってギャグみたいになっているデバッグ出力を眺めたりしています。

それはそれとして、平衡木のいい感じの出力が得られたのでちょっと満足しています。デバッグが捗ります。

あと風邪を引いたり治りかけたりしました。久々におねつを出して懐かしい気持ちになりました。

おわり

おわりです。

*1:より抽象的には、$\frac{f(r)-f(l)}{g(r)-g(l)}$ の形を見たときに、分母・分子をそれぞれ $x$, $y$ 座標の差分だな〜と見れるとよいのかもしれません？

*2:そんなのは気にせず、平衡木から逃げるなという強い意志で勉強する必要がある。

*3:だとえびちゃんは思っています。