Rectangle Store With Constant-Time Point Coverage Counts and Removal by ID

Implement a data structure that stores axis-aligned rectangles, each identified by an id, and answers point queries. It supports three operations: - `add(rect_id, x1, y1, x2, y2)` stores a rectangle under `rect_id`. - `remove(rect_id)` deletes the rectangle stored under `rect_id`. - `count_at(x, y)` returns how many stored rectangles contain the point `(x, y)`. The workload is read-heavy: `count_at` is called far more often than the other two and must run in `O(1)` time, while `add` and `remove` may each take `O(U + 1)` time. The report states these bounds without defining `U`; this version takes `U` to be the number of integer grid points the rectangle covers, with the `+ 1` term being the constant cost every call pays. Write the class, state the time of each method and the memory used, and explain the design choice the bounds imply. The coding round had a third part that the report does not describe, so it is not included here. ```hint Read the bounds backwards If a query may do only constant work, ask where the answer for a point must already be stored before the query arrives, and which operation has to put it there. ``` ```hint Removal needs memory Think about what `remove` receives as input and what it must still know in order to undo exactly what `add` did. ``` ### Constraints and Clarifications - Coordinates are integers and rectangles are axis-aligned. This is assumed because the stated cost of `add` and `remove` is measured in covered grid points. - Rectangles may overlap. A point inside several stored rectangles counts each of them, including two rectangles with identical coordinates stored under different ids. ### Clarifying Questions - Are a rectangle's edges inclusive, so that a point on the boundary is contained, or does it describe a half-open range of cells? - Is the plane bounded, and how large is it? Can a rectangle extend past its edge, and what does `count_at` return for a point outside it? - What should `add` do with an id that is already stored, and `remove` with an id that is not? - Can the corners arrive in either order (for example `x1 > x2`), and can a rectangle be a single row, column or point? - Roughly how many rectangles are stored at once, how large are they, and what is the ratio of reads to writes? ### What a Strong Answer Covers - Reading the complexity targets as a decision to move all the work to writes, so that a query is a single lookup - A per-point count store plus an id-to-rectangle map, so that `remove` undoes exactly what `add` did - Correct handling of overlaps, inclusive boundaries, corner order, duplicate or unknown ids and points outside every rectangle - Time per operation and total memory, including how memory depends on the plane's size versus the points actually covered - At least one alternative, such as a two-dimensional prefix-sum or Fenwick structure, and the workload in which it wins ### Follow-up Questions - Coordinates become very large and a single rectangle can cover millions of points. What breaks, and what would you do instead? - `count_at` must now return the ids of the rectangles at the point, not only how many there are. How do the costs change? - The workload flips and writes become as frequent as reads. Which structure would you use then? - How would you keep `count_at` correct and fast for concurrent readers while an `add` or `remove` is in progress?