| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Hi! I'm searching for a data structure, which efficiently offers the following two operations. On points in a 2D plane.
1) Add a point to the structure.
2) Count the number of points in a given rectangle, which is paralell to x and y axis.
Could anyone tell me if such data structure exists, or even better give me a linik to a simmilar problem on.
Maybe you can use Range Tree on 2 Dimension plane
You need solution for offline problem or online problem?
First all all thanks for reply! I thought of the online problem, but I also know the insert order of the points beforehand, so the offline problem is also sufficient. If there exists a more efficient solution for the offline problem, please tell me this one.
thanks a lot
look at this paper: Range Searching.
Thank's a lot! @ the others do you have a task on codeforces, where this is used!
how you decide that point is parallel to X-axis or Y-axis ....... i think any point is parallel to every axis
a point, i think has no definition of "paralell". I mean the query rectangles sides are paralell to the axis
Finally up to my thought, its possible to add a new point(offline problem) in a 2d range tree by modifying sums in O( log^2 n ). Please tell me if you know any better approach? Queries can than be done in O( log n ) or O( log^2 n ).
Hi, do you have any idea where a problem like this exists in online judge? I am trying to solve this problem http://www.spoj.com/problems/ARNAB4/ however I got file size limit exceeded I am quite sure about my algorithm and wanted to test it. Any help would be appreciated!