Алгоритм пересечения диапазона лучше, чем O (n)?

Так же, как дерево квадратов работает для набора 2d точек, в этом случае должно работать простое двоичное дерево. Постройте дерево со своими диапазонами.

Чтобы объяснить дальше: Каждый узел в дереве содержит два целых числа, начало и конец диапазона, а также двух дочерних узлов, если это не листовой узел. Чтобы найти диапазоны, которые охватывает ваш входной диапазон, затем начните с вершины дерева

  - if the node range intersects the input range:
     - if it's a leaf node, then add the range to your result list
     - if it's not a leaf node, then traverse down to the child nodes and repeat this process.

Это должно быть O (logN)

Дальнейшие детали: Бинарное дерево было бы структурировано как одномерная версия четырехугольного дерева. Каждый узел будет иметь три целых числа (извините, я сказал два выше, но теперь я понимаю, что вам нужно три), наименьшее из которых представляет наименьшее значение самого низкого диапазона, находящегося ниже этого узла, наибольшее представляет наибольшее значение самого высокого диапазона, который ниже этого узел и стержень. Левый дочерний элемент будет простираться от самого нижнего до его стержня. Правый дочерний элемент будет простираться от точки поворота этого узла до самого высокого уровня этого узла. Если есть только один диапазон, который идет от «самого низкого» до «самого высокого», у вас не будет точки поворота, и это будет лист. В идеале вы должны выбрать точки поворота для каждого узла, чтобы дерево оставалось сбалансированным.

Похоже, вам нужен класс, реализующий интерфейс SortedSet. TreeSet - это реализация, которая поставляется с основным API.

Один набор содержит диапазоны, отсортированные по наименьшему значению, а другой - по наибольшему значению.

Затем вы можете реализовать эквивалент алгоритма базы данных, используя наборы в памяти.

Что касается того, действительно ли это быстрее, чем O (n), я не могу сказать.

Это зависит от вашей конкретной проблемы, в связанном вопросе диапазоны, в которых отдельные, общие части отсутствуют, а диапазон поиска может охватывать несколько диапазонов. Если ваша проблема такая же, это действительно просто: Возьмите массив диапазонов, отсортируйте их по наименьшим значениям (поскольку они не перекрываются, это также будет тот же порядок, что и сортировка по их верхним значениям).

Теперь просто выполните поиск бинов для вашего целевого нижнего значения (или меньшего, если неточно) и одного для целевого верхнего значения (или большего, если неточно). Результирующие индексы - это охватываемые диапазоны. Вы должны проверить, включены ли диапазоны в самих индексах или исключены, но это всего лишь две проверки. Общая сложность O (log n).

Когда у меня возникла эта проблема, я использовал отсортированный массив диапазонов и бинарный поиск для поиска пересечений. Это (я считаю) производительность O (log n) с небольшими накладными расходами для работы с перекрывающимися диапазонами.

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

-- РЕДАКТИРОВАТЬ --

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

- КОНЕЦ РЕДАКТИРОВАНИЯ -

Класс Range содержит:

final int                               lower;                                  // lower end of range
final int                               upper;                                  // upper end of range

public int compareTo(Object obj) {
    if (obj==null) { return -1; }

    Range                           oth=(Range)obj;

    if (lower<oth.lower) { return -1; }
    if (lower>oth.lower) { return  1; }
    if (upper<oth.upper) { return -1; }
    if (upper>oth.upper) { return  1; }
    return 0;
    }

Вставка диапазона:

public Builder addRange(int fir, int las) {
    if (fir!=-1) { fir&=0x001FFFFF; }
    if (las!=-1) { las&=0x001FFFFF; }

    if (codepoints==null || codepoints.length==0) {
        codepoints=new Range[]{new Range(fir,las)};
        }
    else {
        int                         idx=Range.findChar(codepoints,fir);
        int                         ins=(idx<0 ? -(idx+1) : idx);

        if (idx<0) {
            if     (ins>0                 && fir==(codepoints[ins-1].upper+1)) { idx=(ins-1); }  // new range adjoins the following range (can't overlap or idx would be >=0)
            else if (ins<codepoints.length && las>=(codepoints[ins  ].lower-1)) { idx=ins;     }  // new range overlaps or adjoins the following range
            }

        if (idx<0) {
            codepoints=(Range[])Util.arrayInsert(codepoints,ins,new Range(fir,las));
            }
        else {
            boolean                 rmv=false;

            for(int xa=(idx+1); xa<codepoints.length && codepoints[xa].lower<=las; xa++) {
                if (las<codepoints[xa].upper) { las=codepoints[xa].upper; }
                codepoints[xa]=null;
                rmv=true;
                }
            if (codepoints[idx].lower>fir || codepoints[idx].upper<las) {
                codepoints[idx]=new Range((codepoints[idx].lower < fir ? codepoints[idx].lower : fir),(codepoints[idx].upper>las ? codepoints[idx].upper : las));
                }
            if (rmv) { codepoints=Range.removeNulls(codepoints); }
            }
        }
    return this;
    }

Двоичный поиск:

static int findChar(Range[] arr, int val) {
    if (arr.length==1) {
        if     (val< arr[0].lower) { return -1; }                             // value too low
        else if (val<=arr[0].upper) { return  0; }                             // value found
        else                       { return -2; }                             // value too high
        }
    else {
        int                             lowidx=0;                               // low index
        int                             hghidx=(arr.length-1);                  // high index
        int                             mididx;                                 // middle index
        Range                           midval;                                 // middle value

        while(lowidx<=hghidx) {
            mididx=((lowidx+hghidx)>>>1);
            midval=arr[mididx];
            if     (val< midval.lower) { hghidx=(mididx-1); }                   // value too low
            else if (val<=midval.upper) { return mididx;     }                   // value found
            else                       { lowidx=(mididx+1); }                   // value too high
            }
        return -(lowidx+1);                                                     // value not found.
        }
    }

Неперекрывающиеся диапазоны:

Подготовить O (n log n):

1. Сделайте массив / вектор диапазонов.
2. Отсортировать вектор по концу диапазона (разорвать связи путем сортировки по началу диапазона)

Поиск:

1. Используйте двоичный поиск, чтобы найти первый диапазон с конечным значением> = TestRange.Start

2. Итератор, начиная с двоичного поиска, пока не найдете Start> TestRange.End:

   2а. Если диапазон, если текущий диапазон находится в пределах TestRange, добавьте его к своему результату.

Редактировать: Похоже, это решение более или менее дерево интервалов. Более полную реализацию дерева интервалов можно найти в здесь.

class TreeNode
{
public:
    long pivot;
    List<Range> leaves;  //Any ranges that intersect the pivot
    TreeNode left;        //Tree nodes that fall to the left of the pivot
    TreeNode right;       //Tree nodes that fall to the right of the pivot
};

Подготовить O (n log n):

1. Создать список диапазонов
2. Выберите точки поворота (возможно, используя отсортированный список дат окончания.) ??
3. Постройте свое дерево.

Поиск:

1. Используйте двоичный поиск, чтобы найти первую точку поворота> = TestRange.End

2. Пройдите по дереву до точки поворота> TestRange.Start

   2а. Добавьте листья к вашему результату.

Пример:

Диапазоны:

• 0–2
• 1-2
• 2–3
• 1–4
• 2–4
• 0–5
• 4–5
• 2–6
• 3–7

Дерево:

                             4
               --------------+------------------
               3             |                 7
               |            1-4                |
               |            2-4                |
               |            0-5                |
               |            4-5                |
      ---------+------                 --------+--------
      2        |    null              6        |       null
 -----+----   2-3                 ----+----   3-7
null  |  null                   null  |  null    
     0-2                             2-6
     1-2

Перекрывающиеся диапазоны:

Подготовить O (n log n):

1. Сделайте массив / вектор диапазонов.
2. Отсортировать вектор по концу диапазона (разорвать связи путем сортировки по началу диапазона)

3. Сделайте второй вектор из целых чисел. Это точка, в которой вы можете прекратить поиск.

   int stop[size];
   stop[size-1] = Ranges[size - 1].start;
   for (int i = size - 2; i >= 0; i--)
   {
       stop[i] = min(Ranges[i].start, stop[i+1]);
   }
   

Поиск:

1. Используйте двоичный поиск, чтобы найти первый диапазон с конечным значением> = TestRange.Start

2. Итератор, начиная с двоичного поиска до остановки [i]> TestRange.End:

   2а. Если диапазон, если текущий диапазон находится в пределах TestRange, добавьте его к своему результату.

Стандартный подход - использовать дерево интервалов.

In computer science, an interval tree is a tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is often used for windowing queries, for instance, to find all roads on a computerized map inside a rectangular viewport, or to find all visible elements inside a three-dimensional scene. A similar data structure is the segment tree.

The trivial solution is to visit each interval and test whether it intersects the given point or interval, which requires O(n) time, where n is the number of intervals in the collection. Since a query may return all intervals, for example if the query is a large interval intersecting all intervals in the collection, this is asymptotically optimal; however, we can do better by considering output-sensitive algorithms, where the runtime is expressed in terms of m, the number of intervals produced by the query. Interval trees have a query time of O(log n + m) and an initial creation time of O(n log n), while limiting memory consumption to O(n). After creation, interval trees may be dynamic, allowing efficient insertion and deletion of an interval in O(log n). If the endpoints of intervals are within a small integer range (e.g., in the range [1,...,O(n)]), faster data structures exist[1] with preprocessing time O(n) and query time O(1+m) for reporting m intervals containing a given query point.

Если диапазоны перекрываются, и кто-то хочет получить все диапазоны, которые перекрывают (или содержат) заданный целевой диапазон, большинство вышеперечисленных решений, похоже, не работают.

Как отмечали некоторые, если (в худшем случае) все диапазоны пересекают целевой диапазон (например, если целевой диапазон равен {0..MAXINT} или подобный), то, конечно, для возврата требуется O (n) n диапазонов.

Но разве это не интересный и типичный / средний случай, когда только очень небольшой% из n общих диапазонов действительно пересекает целевой диапазон? Назовите число, которое делать пересекает "m" - в этом случае вы, вероятно, сможете сделать так же хорошо, как O (m). И если n = 10 ^ 9 и m = 10, это принципиальная разница.

Рассмотрим простой случай текстового документа, в котором различные области размечены для их «типа» - возможно, вы хотите найти все размеченные блоки, которые содержат или пересекают заданный непрерывный диапазон текста (например, абзац). В HTML, XML или аналогичных они могут быть только предками текстовых узлов, содержащих хотя бы некоторые символы целевого диапазона. В типичных представлениях с родительскими указателями в каждом узле это O (m) - намного лучше, чем O (n), особенно потому, что m (для коротких или синхронных целевых диапазонов) просто глубина вложения дерева, которая имеет тенденцию быть даже ниже, чем ln (n), потому что большие XML-документы на практике становятся не глубже, а пышнее.

Интересный случай сложнее: что, если ваши «элементы» не образуют дерево, как в XML, но могут перекрываться, как в MECS, CLIX, LMNL и некоторых других системах? Вы по-прежнему хотите найти все регионы / «элементы», которые перекрывают вашу цель, но их не так легко организовать.

С другой стороны, у вас должно получиться очень хорошо, потому что размеченные диапазоны во многих приложениях чаще всего маленькие - в книге гораздо больше слов, предложений и абзацев, чем глав. Таким образом, даже если может быть огромное количество диапазонов, которые начинаются до цели, и огромное количество, которые заканчиваются после нее, пересечение в среднем будет очень маленьким.

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