概要
問題文 → ■
公式解説 → ■, p.86
自分の提出 → ■
解法
Euler Tour をとって、Euler Tour における頂点順を $x$ 座標、木における深さを $y$ 座標と見なすことで、次のクエリ処理に帰着できます：
- 矩形領域内のデータ点に対して、$v$ を加算する
- 矩形領域内のデータ点の値の総和を求める
- データ点を追加する
これが 1 次元の区間クエリだと、遅延セグメント木でできます。2 次元の矩形クエリでも、kd tree を用いると今回の矩形クエリを処理することができます。kd tree による矩形クエリは点の個数の $1/2$ 乗の時間計算量で行えて、本問題は $O(N+Q\sqrt{N+Q})$ 時間で解くことができます。
参考文献：https://trap.jp/post/1489/
kd tree による遅延伝播の verify 問題としてもちょうどいい気がします。
