Быстрые запросы в плоскости

Question

Задача Я должен поддерживать Q-запросы набора n 2-D точек в декартовой плоскости, лежащих в [0, M] x [0, M]. Очки указываются заранее.

Каждый запрос попросит меня подсчитать количество точек, заключенных в прямоугольник (x1, y1) * (x2, y2). (прямоугольник, выровненный по оси).

ограничение
< M 10000

Я хочу знать больше об используемых алгоритмах. Можно ли выполнять эти запросы более эффективно использовать эту информацию, чтобы все точки и запросы даются заранее и координаты точек ограничены и т.д.

Вариант: Вместо п точек, чтобы начать с, Можем ли мы добавить n ориентированных по оси прямоугольных патчей точек, как n добавить операцию в нашу структуру данных, а затем ответить на одни и те же запросы. [ленивый сегмент деревьев типа подхода].

Answer 1

Это классическая проблема 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)