二次元平面上に点が散らばっているとき、任意の長方形の中に入っている点の数を数える。平面の大きさがだいたい$10^5\times 10^5$くらいまでいける。通常の二次元累積和だとこの大きさの平面を数えるのは無理。ただ、点の数も$10^5$くらいまでじゃないと数えられないことに加えて、知りたい長方形を最初に列挙できる必要があることにも注意。
最初に知りたい長方形を左端と右端の二つの質問クエリに分けて列挙しておく。次に点と質問を合わせて$x$座標でソートする。ソートしたら$x$座標の小さいほうから順にみて、点が来たらその$y$座標に+1して、質問が来たら求められている範囲の総和を答える。この操作はBITやセグ木を使えば全部でNlogNくらいでできる。質問の答えを持っておくのはmapやunordered_mapなどを使えばよい。
画像では、質問クエリ$Q_1, Q_2$に挟まれた長方形の中にある点の数を求めようとしている。$x=0$からBIT/セグ木をスライドさせていくイメージで、たとえば$y=3$の点が来たら3番目のノードに+1するなどして今までに見た点を数えていく。そして質問クエリが来たらその範囲にいままで出てきた点の数を答える。長方形の右端と左端それぞれを質問クエリにして入れておけば、右端から左端を引くことで中にある点の数がわかる。