はじめに

昨日、arXiv に The Li-Chao Tree: Algorithm Specification and Analysis というペーパーが載っているのを見ました。これの author はおそらく Li-Chao Tree を開発した本人なので、せっかくですし読んで、ついでにこの辺の話をまとめたいと思います。Li-Chao Tree は個人的にもお気に入りの構造です。

本文では時々今回のペーパーを参照するので、横で一緒に見ながら読んでいただくことを推奨します。

導入

次のような問題を考えます :

2 種類のクエリがたくさん与えられるので、処理してください。

1. 追加クエリ : 直線 $y = kx + b$ を追加する。
2. 最小値クエリ : ある $x_0$ について、$\min_i \{k_i x_0 + b_i\}$ を求める。

幾何でよくある問題です。AtCoder では出ることが少ないかもしれませんが、ICPC や Ucup ではそこそこ出ることがある気がします。私も何回か解いたことがあります。

CHT のはなし

若干本筋から逸れますが、まずはこの問題そのものについて考えてみましょう。

少し観察をすると、次の事実が分かります。

• 最小値を示す部分について、傾きは単調減少である。すなわち、最小値を示す部分は上に凸である。

凸な図形に関するアルゴリズムといえば、凸包を思い浮かべる方が多いかと思います。先の性質を用いると、凸包を少しいじったテクニックで解くことができます。凸包を少しいじったテクニックが CHT; Convex Hull Trick です。

今回は、Li-Chao Tree を用いた解法を紹介しますが、次のような実装もあります :

• 直線の追加クエリについて、傾きが単調な順序で入力されることが保証されている場合、std::vector などの配列を用いて解くことができます。こちらは蟻本に詳しいことが書かれていたと思います。
  • さらに、最小値クエリも単調の場合、直線が端から順に不要になっていくので、std::deque を用いて実装などするとならし $O(1)$ 時間で各クエリ処理できます。
• 連想配列を用いて実装する方法があります。少し複雑になってしまいがちなことと、適当にやると log が 2 個付くことがあるらしく、私はあまりこっちの実装はしたことがないです。

Li-Chao Tree

直線に関する基本的かつ重要な性質として、次があります。

• 2 つの傾きの異なる直線が交わるとき、交点はただ 1 つである。

これを考えると、特定の区間において 2 直線の値を比較したとき、少なくとも区間の半分においては一方の直線が他方より小さい値を取ることがわかります。具体的に、区間 $[l, r]$ について考えたとき、中点 $m = (l + r) / 2$ において一方の直線が他方より小さい値を取るとき、この直線は区間の半分以上において他方より小さい値を取ります (ペーパーの Figure 1 を参照のこと)。

アルゴリズム

Li-Chao Tree は、この性質を用いた構造です。以下に Definition を述べます :

Def. (Li-Chao Tree)

Li-Chao Tree は、特定の区間 $[L, R]$ を管理する Binary Tree である。

• 各頂点は区間 $[l, r] \in [L, R]$ (と中点 $m = (l + r) / 2$) と、高々 1 つの直線 $f(x) = kx+b$ を持つ。
• 各頂点に格納される直線は、その区間の中点において最小値をとる直線である。
• 各頂点について、左の子は $[l, m]$ を、右の子は $[m, r]$ を管理する。
• 最初は $[L, R]$ を管理する 1 頂点からなる木である。

この構造を用いて、追加クエリ・最小値クエリを処理することを考えましょう。

簡単のため、最小値クエリで与えられる $x$ はすべて整数であることを仮定しますが、整数でなくても精度に合わせて適切に離散化すればよいです。

また、ここで一つの定数を導入します : $C = \frac{\mathrm{coordinate\ range}}{\mathrm{precision\ level}}$

例えば、全体の区間が $[0, 10^9]$ で、$10^{-6}$ ぐらいの精度が必要な場合、$C = 10^{15}$ です。

追加

root から leaf まで辿っていきます。

• 現在の頂点に直線が保存されていない場合
  • そこに新しい直線が保存され、処理が終了する。
• 現在の頂点に直線が保存されている場合
  • 区間の中点で比較し、より小さい値を取る方の直線がこのノードに保存され、そうでない方の直線は適切な子頂点に送られる。

追加にかかる計算量は $O(\log{C})$ です。

最小値

root から辿っていきます。$x$ を含む区間をどんどん辿っていきます。leaf まで到達したらその頂点に答えの直線が保存されているので、それを用いて計算すれば最小値が分かります。 最小値を求めるのにかかる計算量は $O(\log{C})$ です。

実装などについては、ペーパーに疑似コードが載っていますので確認してみてください (Algorithm 1, 2)。

線分に対するクエリ

直線だけでなく、線分に対するクエリも Li-Chao Tree で処理することができます。これは、線分の区間を高々 $O(\log{C})$ 個の区間に分割して、それぞれに対して追加クエリを処理すればよいです。この処理は $O(\log^2{C})$ かかります。実装は Algorithm 3 を参照してください。

文章ではこの後に、計算量解析など理論的な解析が書かれていますので、そちらも是非読んでみてください。

Convex Hull Trick の強み

幾何の問題でよく使われるといいましたが、この CHT は dp に利用することができます。 $\mathrm{dp}[i] := \min_{1 \leq j < i} \{a(j)b(i) + c(j)\} + d(i)$ の形の dp は、一次関数の見た目のものの最小を取っていそうなので、CHT を使えば解けます。

以降、ネタバレを含みます。

例 1

こういう時は EDPC ですね。

$N$ 個の足場があり、それぞれに $h_1, h_2, ..., h_N$ が割り振られている (h_1 < h_2 < \cdots < h_N)。 足場 $i$ からコスト $(h_j - h_i)^2 + C$ を消費して足場 $j\ (i + 1 \leq j \leq N)$ へ行くことを考えるとき、$1$ から $N$ にたどり着くまでに消費するコストの総和の最小値を求める。 (出典 : https://atcoder.jp/contests/dp/tasks/dp_z)

$\mathrm{dp}(i)$ を $i$ 番目の足場まで行くのにかかるコストの最小値としておきます。とりあえず式に起こすと、

これを展開してあげましょう。

$j$ に関係のない部分は $\min$ の括弧から外せるので、外して整理すると、

これは先ほどの形そのものです。よって CHT を使って解くことができます。もちろん Li-Chao Tree 使えます。

submission : https://atcoder.jp/contests/dp/submissions/74001321

私の Li-Chao Tree は ICPC に持って行っているライブラリなので、実装量はかなり少ないです。

例 2

関数が互いに高々 1 つの交点をもつことが本質です。

$N$ 種類の品物が無限にあって、重み・価値がそれぞれ assign されている。容量 $W$ のバッグに品物を選んで入れる。$i$ 種類目の品物を $k_i$ 個選んだ時のうれしさを $k_iv_i - k_i^2$ としたとき、うれしさの総和の最大値を求める。 出典 : https://atcoder.jp/contests/abc373/tasks/abc373_f

ナップサック問題の dp と言ったら、$\mathrm{dp}(i, j)$ を $i$ 種類目までのうちから重みの総和が $j$ となるように選んだ時の～という風に取るのが自然ですね。今回もそれでうれしさの最大値を dp に持たせてみましょう。愚直にやると、

です。

かなり面倒なので観察します。$i$ を固定して $j$ を動かすことを考えてみましょう。 実験すると、$\mathrm{dp}(i, j)$ と $\mathrm{dp}(i, j + w_i)$ は同じように計算できそうだということが分かります。繰り返すと、本質的には $j = 0, ..., w_i - 1$ に対して $\mathrm{dp}(i, j)$ を求めることが重要そうに見えます。 $j = q \cdot w_i + r\ (0 \leq r < w_i)$ とします。$r$ を固定し、$q$ の部分を動かすことを考えてみましょう。すると、先の式は次のようになります :

$f(k, x) = \mathrm{dp}(i - 1, r + kw_i) + (x - k)v_i + (x-k)^2$ として、$r$ を固定したので同じ $r$ でまとめてあげます :

すると、$dp(i,j)=\max_{k=0, \dots, q}\{f(k, q) \in S(r)\}$ というような形にできます。

こうすると、結局 $S(r)$ をうまく CHT で持たせればうまくいくことが分かります。

考察だけして実装サボってるので後はお願いします。

おわり

おわりです。