更快的平面查询
Faster Queries in plane
问题 我必须支持笛卡尔平面中位于 [0,M]x[0,M] 中的一组 n 个二维点的 Q 查询。提前给分
每个查询都要求我计算矩形 (x1,y1)*(x2,y2) 中包含的点数。 （轴对齐矩形）。
约束
0 < M < 10000
我想详细了解所使用的算法。我们能否使用预先给出所有 点和查询的信息更有效地执行这些查询 并且点的 坐标是有界的 等。
变体：我们可以在我们的数据结构中添加 n 个轴对齐的矩形点作为 n 个添加操作，而不是 n 个点开始，然后回答相同的查询. [惰性段树的一种方法]。
这是一个经典的 2d Binary Indexed Tree 问题。二叉索引树可以给你从 (0,0) 到 (x,y) 的矩形中有多少个点，现在如果你想知道 (x1,y1) 和 (x2) 表示的矩形中有多少个点,y2), 首先你要找到矩形另外两个角点的坐标。设 pUL、pUR、pBL、pBR 是矩形的四个角点，分别代表左上角、右上角、左下角和右下角。通过使用包含 - 排除逻辑，这个矩形中包含的点数是。
q(p) // query on 2D-BIT for point p which gives how many dots are in
// rectangle represented by (0,0) and (p.x, p.y)
result = q(pUR)-q(pUL)-q(pBR)+p(pBL)
问题 我必须支持笛卡尔平面中位于 [0,M]x[0,M] 中的一组 n 个二维点的 Q 查询。提前给分
每个查询都要求我计算矩形 (x1,y1)*(x2,y2) 中包含的点数。 （轴对齐矩形）。
约束
0 < M < 10000
我想详细了解所使用的算法。我们能否使用预先给出所有 点和查询的信息更有效地执行这些查询 并且点的 坐标是有界的 等。
变体：我们可以在我们的数据结构中添加 n 个轴对齐的矩形点作为 n 个添加操作，而不是 n 个点开始，然后回答相同的查询. [惰性段树的一种方法]。
这是一个经典的 2d Binary Indexed Tree 问题。二叉索引树可以给你从 (0,0) 到 (x,y) 的矩形中有多少个点，现在如果你想知道 (x1,y1) 和 (x2) 表示的矩形中有多少个点,y2), 首先你要找到矩形另外两个角点的坐标。设 pUL、pUR、pBL、pBR 是矩形的四个角点，分别代表左上角、右上角、左下角和右下角。通过使用包含 - 排除逻辑，这个矩形中包含的点数是。
q(p) // query on 2D-BIT for point p which gives how many dots are in
// rectangle represented by (0,0) and (p.x, p.y)
result = q(pUR)-q(pUL)-q(pBR)+p(pBL)