Range Tree のメモ

はしがき

タイトル通りです。可読性は低いです。やる気が出たら可読性を上げます。

todo

point add rectangle sum （https://judge.yosupo.jp/problem/point_add_rectangle_sum）を解きます。

tree.build()

まず、登場する点をすべて先読みし、ソート済みの点列$${P = ((x_1, y_1), \cdots, (x_k, y_k))}$$を作ります。この$${P}$$から$${segx}$$を構築します。$${segx}$$の頂点$${[l, r]}$$に持たせる要素は、$${sorted((x_l, y_l), \cdots, (x_r, y_r))}$$および$${sorted((y_l, x_l), \cdots, (y_r, x_k))}$$です。

また、頂点$${[l, r]}$$に長さ$${r-l+1}$$の$${segy}$$を構築します。$${segy}$$は重みの区間和を求めるために使います。

構築はソートがボトルネックで、たぶん$${O(n\log ^ 2 n)}$$です。

tree.add(x, y, w)

$${P}$$における$${p=pos(x, y)}$$は lower_bound で求められます。

頂点$${[p, p]}$$の上にあるすべての頂点$${[l, r]}$$に対して$${segy}$$の変更を行います。$${sorted((y_l, x_l), \cdots, (y_r, x_k))}$$における$${q=pos(y, x)}$$も lower_bound で求められます。あとは$${segy.add(q, w)}$$をすればよいです。

各$${segy.add(q, w)}$$で$${O(\log n)}$$、頂点$${[p, p]}$$の上にある頂点の個数が$${O(\log n)}$$なので、$${O(\log ^ 2 n)}$$です。

tree.sum(l, r, d, u)

頂点$${[l2, r2]}$$の寄与を考えます。$${intersect([l, r], [l2, r2])=no}$$ならば寄与は$${0}$$です。$${intersect([l, r], [l2, r2])=partial}$$ならば、子の頂点を見ればよいです。$${intersect([l, r], [l2, r2])=overlap}$$ならば頂点$${[l2, r2]}$$の$${segy}$$で寄与を計算します。

overlap している、というのは$${l\le x_{l2}\le x_{r2}\le r}$$という意味です。

これは簡単で、$${sorted((y_l, x_l), \cdots, (y_r, x_k))}$$に対して$${(d, -inf), (u, inf)}$$で lower_bound したものを$${p, q}$$として$${segy.sum(p, q)}$$が寄与になります。

たぶん全体で$${O(\log ^ 2 n)}$$になるはず。

おわり

segtree を 2 個書きます。だるいね。

やる：実装して、実装例を貼る