【模板】二维数点

posted on 2022-10-23 13:50:24 | under 模板 | source

problem

给定一个二维平面，多次询问 \(x\in[l_x,r_x],y\in[l_y,r_y]\) 的点有多少个。

solution 1（静态+在线）：可持久化线段树

将 \(x\in[1,l]\) 的点，放入第 \(l\) 棵线段树中，询问时就是在第 \(l_x-1,r_x\) 这两棵线段树上求区间和。显然可以用可持久化线段树维护。

solution 2（静态+离线）：树状数组

将询问 \((l_x,r_x,l_y,r_y)\) 拆成 \((1,r_x,1,r_y)-(1,l_x-1,1,r_y)-(1,r_x,1,l_y-1)+(1,l_x-1,1,l_y-1)\)。

不需要维护每个前缀，而只需要扫描线过去即可。树状数组。