range tree

とりあえず2次元で,クエリが点追加と矩形カウントできるデータ構造の話をします.まずある点(a,b)から左下にある点の数を数えられれば矩形カウントが出来ることに注意.
座標幅は縦横ともにL,クエリN個とします(当然点の数もN以下)

蟻本にも載ってる,マージソートの途中経過をそのまま保存したようなsegtreeを使えば,前計算O(Nlog^2N),クエリO(log^2N),全体でO(Nlog^2N),空間O(NlogN)で出来る(logが上に凸なので,まとめてlogとかにはならないことに注意(よくある木DPみたいな)) ただしこれは点追加ができない.

点追加ができなくていいなら計算量すら落とせて,点を左から順番に追加していったと考えて,クエリ(a,b)があれば,a以下までを追加したタイミングでで下に何個点があるか を普通の1次元segtreeを使って求めれば良い 時間空間ともにO(NlogN) 横方向を時間軸だと思ってsegtreeを左から進めていくイメージ.

点追加がしたい.
クエリが先読みできる場合.
蟻本のやつに+点追加ができればいいので,segtreeに持たせるのをvectorじゃなくてBITにすればよい.NlogN個のBIT全てで座標幅Nにしてたらアホなので,そこに出てくるとこを座圧(これはさっきのマージソートの途中経過を持っとけばできる)すれば,時間O(Nlog^2N),空間O(NlogN).

さっきまでのは座圧して座標幅をNだと思えたので計算量にLは出てこなかったが,先読みできないと話は違ってくる.

今L=1e9くらいのイメージで話してます
まず横幅が大きいと難しいので,O(N)だとしてください
さっきと同様横向きにsegtreeを持ちます.各ノードには平行二分探索木をのせます(あっ(察し))すると時間計算量はさっきと一緒で,空間も全体でO(NlogN)に出来る.

横幅も大きい時なんですが,横も自前平衡二分木にすればよくて,mergeがO(1)で出来ない(mergeする二つの木の大きさをnとしてO(nlogn))ためこれも計算量は全体でO(Nlog^2N) 空間がO(N)になってる・・・?(書いててびっくりした)

最後のは実装してないし計算量もほんとか怪しいので信じないでください