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)\)。
不需要维护每个前缀,而只需要扫描线过去即可。树状数组。
标签:树状,线段,数点,solution,二维,询问,模板 From: https://www.cnblogs.com/caijianhong/p/16863462.html