Количество элементов в интервале (x,y) за время (logn)(logn)
Домашнее задание
Мне нужно использовать структуру данных + алгоритм, который возвращает количество элементов в диапазоне, состоящем из 2 (x,y) значений (т.е. возвращает количество элементов, попадающих в прямоугольный диапазон на плоскости xy) в O(logn* LOGN).
Я рассматриваю две возможности, kd-дерево и дерево диапазона. KD-дерево хорошо подходит для этого, потому что оно может находить элементы в пределах диапазона в O(logn + k) (для k элементов оно должно сообщать). Но мне не нужно сообщать об элементах, мне просто нужно вычислить количество элементов в пределах диапазона.
Дерево диапазонов может работать в этом, у меня может быть свойство в каждом узле, которое содержит сколько их меньше, чем он сам. Таким образом, я могу определить, сколько элементов меньше определенного значения в O(logn) раз (перейдя к двум границам и найдя разницу в количестве узлов, которые меньше друг друга). Тем не менее, я не думаю, что это будет работать для наборов данных, которые имеют (x, y) измерение.
Я на правильном пути?
1 ответ
То, что вы описали, представляет собой онлайн-задачу двумерного подсчета ортогонального диапазона. "Онлайн" означает, что после предварительной обработки данных запросы приходят один за другим. "Ортогональный" указывает, что диапазоны являются прямоугольниками, ориентированными по оси. И, в отличие от отчетов о диапазоне, при подсчете диапазона учитывается только количество элементов, попадающих в диапазон.
Дерево kd с каждым узлом, хранящим общее количество узлов под ним, может выполнить подсчет диапазона в O(n^(1-1/k)) в худшем случае. Это связано с тем, что любой ортогональный диапазон может пересекать самое большее O(n^(1-1/k)) листьев дерева kd. В 2-м случае это означает, что запрос подсчета диапазона может быть выполнен за O(sqrt(n)), что хуже, чем требуемый O((log(n))^2).
Ваш третий абзац не имеет смысла, так как дерево диапазонов определено в больших измерениях. Фактически, это учебное решение для многомерных задач подсчета ортогональных диапазонов. Он решает в режиме онлайн двумерный подсчет ортогональных диапазонов за ровно O ((log (n)) ^ 2) времени запроса. Я бы порекомендовал вам прочитать одну основополагающую статью " Многомерный принцип" разделяй и властвуй "", написанную Джоном Луи Бентли, одним из нескольких людей, независимо обнаруживших дерево рангов. Соответствующий раздел 2.1.2.
Поскольку это домашнее задание, я не буду вдаваться в подробности, но я, наверное, уже слишком много сказал.