はじめに
領域木はいいぞ
できること
二次元空間を考える．
重み付きの点N個を前もって与える．
矩形内の重みの総和クエリがO((logN)2)でできる．
簡単に言えば，二次元空間に広がる点がN個あって，矩形内の点数のカウントクエリがO((logN)2)だよ
え，それそんな嬉しい？
嬉しい．
区間の種類数クエリがオンラインで解けるようになる．
はい． Submission #19394286 - AtCoder Beginner Contest 174
配列の添え字の範囲，値の範囲に関して総和クエリを投げれる
配列vがある． そのうち，添え字が[i, j), 値が[l, r)のもののなんらかの総和，みたいなのが答えられる． たまにほしくない？
他の例
ABC202 - Eがやるだけ 問題概要は略． オイラーツアーしておいて頂点を並べて置き，xの値がこの並べたときのindex, yの値が根からの距離で領域木を構築しておく． 各クエリを処理するには[in[u], out[u]) * [d, d+1)のクエリを投げればオンラインで倒せる． in, outはオイラーツアーの時に作れるヤツ
https://atcoder.jp/contests/abc202/submissions/22805167
仕組み
x座標を基準にセグメント木を構築するイメージ． セグメント木のノードはソートされたy座標を持つ． セグメント木のノードに訪れるたびに，y座標で当該範囲がどこになるかを二分探索し，累積和してあげる．
実装
https://mugen1337.github.io/procon/DataStructure/RangeTree.cppmugen1337.github.io
わかりやすい資料
verify
発展
更新可能にできるか
X座標のみ前もってわかっていればY側は更新可能にできたりすると思います． ソートされた配列ではなく平衡二分探索木などをのせてみます． 昔書きましたが，ゲロみたいに重かったのでここではあまり触れません
Fractional Cascading
工夫することでクエリあたりO(logN)にできるようです． 昔書いてみましたが，定数倍の関係で競プロの問題ではそこまで速さが変わらなかった記憶があります．そんなことないよ！っていう例があれば知りたい
あ
なんか他にも僕の知らないこといっぱいありそう
おわりに
割と仕組みわかりやすくない？ そのわりにはつよくない？ そうでもない？ そう...
