Эффективная структура данных для хранения длинной последовательности (в основном последовательных) целых чисел

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

Особенность входных данных, которые я хотел бы использовать (чтобы требовать "эффективности" ), заключается в том, что долготы будут в основном последовательными. Могут отсутствовать значения. И значения могут взаимодействовать с не по порядку.

Я бы хотел, чтобы структура данных поддерживала следующие операции:

addVal (n): добавить одно значение, n
addRange (n, m): добавить все значения между n и m, включительно
delVal (n): удалить одно значение, n
delRange (n, m): удалить все значения между n и m, включительно
containsVal (n): возвращает ли одно единственное значение n в структуре
содержит Range (n, m): возвращает ли все значения между n и m, включая, существуют в структуре

По сути, это более конкретный тип структуры данных Set, который может использовать непрерывность данных для использования меньше, чем O (n) памяти, где n - это количество сохраненных значений.

Чтобы быть ясным, хотя я считаю, что эффективная реализация такой структуры данных потребует, чтобы мы хранили внутренние интервалы, которые не видны или релевантны пользователю. Существуют несколько деревьев интервалов, которые хранят несколько интервалов отдельно и позволяют операциям находить количество интервалов, которые перекрываются с данной точкой или интервалом. Но с точки зрения пользователя это должно вести себя точно как набор (за исключением операций на основе диапазона, поэтому массовые добавления и удаления можно эффективно обрабатывать).

Пример:

dataStructure = ...
dataStructure.addRange(1,100) // [(1, 100)]
dataStructure.addRange(200,300) // [(1, 100), (200, 300)]
dataStructure.addVal(199) // [(1, 100), (199, 300)]
dataStructure.delRange(50,250) // [(1, 49), (251, 300)]

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

Ответ 1

Если вам не нужны дубликаты, ваши интервалы не перекрываются. Вам нужно создать структуру, которая поддерживает этот инвариант. Если вам нужен запрос, например numIntervalsContaining (n), то это другая проблема.

Вы можете использовать BST, который хранит пары конечных точек, как в С++ std::set<std::pair<long,long>>. Интерпретация заключается в том, что каждая запись соответствует интервалу [n,m]. Вам нужен слабый порядок - это обычный целочисленный порядок на левой конечной точке. В качестве [n,n] вставляется один int или long n. Мы должны поддерживать свойство, что все интервалы node не перекрываются. Краткая оценка порядка ваших операций следующая. Поскольку вы уже обозначили n, я использую n для размера дерева.

addVal (n): добавьте одно значение, n: O(log N), то же, что и std::set<int>. Поскольку интервалы не перекрываются, вам нужно найти предшественника n, который можно сделать в O(log N) времени (разбить его на случаи, как в https://www.quora.com/How-can-you-find-successors-and-predecessors-in-a-binary-search-tree-in-order). Посмотрите на правую конечную точку этого предшественника и увеличьте интервал или добавьте дополнительный node [n,n], если это необходимо, который по порядку останова будет всегда правильным. Обратите внимание, что если интервал расширен (вставляя [n+1,n+1] в дерево с node [a,n], образуя node [a,n+1]), он может теперь столкнуться с следующей левой конечной точкой, требуя другого слияния. Поэтому есть несколько краевых случаев. Немного сложнее, чем простой BST, но все же O(log N).
addRange (n, m): O(log N), процесс похож. Если введенный интервал нетривиально пересекается с другим, объедините интервалы так, чтобы сохранялось неперекрывающееся свойство. В худшем случае производительность O(n), как указано ниже, поскольку верхний предел количества подынтервалов, потребляемых тем, который мы вставляем, не существует.
delVal (n): O(log N), еще раз O(n) наихудший случай, так как мы не знаем, сколько интервалов содержится в интервале, который мы удаляем.
delRange (n, m): удалить все значения между n и m, включительно: O(log N)
containsVal (n): возвращает ли одно единственное значение n в структуре: O(log N)
содержит Range (n, m): возвращает ли все значения между n и m включительно в структуру: O(log N)

Обратите внимание, что мы можем поддерживать свойство без перекрывания с правильными методами add() и addRange(), оно уже поддерживается методами удаления. Нам нужно O(n) хранение в худшем случае.

Обратите внимание, что все операции O(log N), а вставка диапазона [n,m] не похожа на O(m-n) или O(log(m-n)) или что-то в этом роде.

Я предполагаю, что вам не нужны дубликаты, просто членство. В противном случае вам может понадобиться дерево интервалов или дерево KD или что-то еще, но они более важны для данных float...

Ответ 2

Другой альтернативой может быть структура данных каната (https://en.m.wikipedia.org/wiki/Rope_(data_structure)), которая, как представляется, поддерживает операции, которые вы запрашиваете, реализована в O(log n) время. В отличие от примера в Википедии, ваш хранит [start,end] вместо строковых подпоследовательностей.

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

Ответ 3

Кажется, что интервальные деревья направлены на сохранение перекрывающихся интервалов, в то время как в вашем случае это не имеет смысла. Дерево интервалов может содержать миллионы небольших перекрывающихся интервалов, которые вместе образуют только несколько длинных неперекрывающихся интервалов.

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

Это похоже на работу для скромного связанного списка. При вставке нового интервала вы должны:

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

Удаление интервала будет в основном одинаковым: вы обрезаете интервалы, в которые находится начальная точка и конечная точка, и удалите все интервалы между ними.

Средняя и наихудшая сложность этого - N/2 и N, где N - количество интервалов в связанном списке. Вы можете улучшить это, добавив метод, чтобы избежать необходимости перебирать весь список, чтобы найти начальную точку; если вы знаете диапазон и распределение значений, это может быть что-то вроде хеш-таблицы; например если значения от 1 до X и распределение равномерно, вы сохраните таблицу длины Y, где каждый элемент указывает на интервал, начинающийся до значения X/Y. Добавляя интервал (A, B), вы просматриваете таблицу [A/Y] и начинаете итерацию по связанному списку оттуда. Выбор значения для Y будет определяться тем, сколько места вы хотите использовать, по сравнению с тем, как близко вы хотите добраться до фактического положения начальной точки. Тогда сложности будут уменьшаться на множитель Y.

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

Здесь начинается пример кода с тремя функциями диапазона, но без дальнейшей оптимизации:

function Interval(a, b, n) {
    this.start = a;
    this.end = b;
    this.next = n;
}

function IntervalList() {
    this.first = null;
}

IntervalList.prototype.addRange = function(a, b) {
    if (!this.first || b < this.first.start - 1) {
        this.first = new Interval(a, b, this.first); // insert as first element
        return;
    }
    var i = this.first;
    while (a > i.end + 1 && i.next && b >= i.next.start - 1) {
        i = i.next;                                  // locate starting point
    }
    if (a > i.end + 1) {                             // insert as new element
        i.next = new Interval(a, b, i.next);
        return;
    }
    var j = i.next;
    while (j && b >= j.start - 1) {                  // locate end point
        i.end = j.end;
        i.next = j = j.next;                         // discard overlapping interval
    }
    if (a < i.start) i.start = a;                    // update interval start
    if (b > i.end) i.end = b;                        // update interval end
}

IntervalList.prototype.delRange = function(a, b) {
    if (!this.first || b < this.first.start) return; // range before first interval
    var i = this.first;
    while (i.next && a > i.next.start) i = i.next;   // a in or after interval i
    if (a > i.start) {                               // a in interval
        if (b < i.end) {                             // range in interval -> split
            i.next = new Interval(b + 1, i.end, i.next);
            i.end = a - 1;
            return;
        }
        if (a <= i.end) i.end = a - 1;               // truncate interval
    }
    var j = a > i.start ? i.next : i;
    while (j && b >= j.end) j = j.next;              // b before or in interval j
    if (a <= this.first.start) this.first = j;       // short-circuit list
    else i.next = j;
    if (j && b >= j.start) j.start = b + 1;          // truncate interval
}

IntervalList.prototype.hasRange = function(a, b) {
    if (!this.first) return false;                   // empty list
    var i = this.first;
    while (i.next && a > i.end) i = i.next;          // a before or in interval i
    return a >= i.start && b <= i.end;               // range in interval ?
}

IntervalList.prototype.addValue = function(a) {
    this.addRange(a, a);                             // could be optimised
}

IntervalList.prototype.delValue = function(a) {
    this.delRange(a, a);                             // could be optimised
}

IntervalList.prototype.hasValue = function(a) {
    return this.hasRange(a, a);                      // could be optimised
}

IntervalList.prototype.print = function() {
    var i = this.first;
    if (i) do document.write("(" + i.start + "-" + i.end + ") "); while (i = i.next);
    document.write("<br>");
}

var intervals = new IntervalList();
intervals.addRange(100,199);
document.write("+ (100-199) &rarr; "); intervals.print();
intervals.addRange(300,399);
document.write("+ (300-399) &rarr; "); intervals.print();
intervals.addRange(200,299);
document.write("+ (200-299) &rarr; "); intervals.print();
intervals.delRange(225,275);
document.write("− (225-275) &rarr; "); intervals.print();
document.write("(150-200) ? " + intervals.hasRange(150,200) + "<br>");
document.write("(200-300) ? " + intervals.hasRange(200,300) + "<br>");

Ответ 4

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

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

Возможным решением для этого может быть сохранение значений (а не начальной и конечной точек интервалов) в N-ary tree, где каждый node представляет диапазон и хранит две N-битовые карты, представляющие N поддиапазонов, и все ли присутствующие значения в этих поддиапазонах присутствуют, все отсутствуют или смешиваются. В случае смешанного будет указатель на дочерний элемент node, который представляет этот диапазон.

Пример: (используя дерево с коэффициент ветвления 8 и высоту 2)

full range: 0-511 ; store interval 100-300

0-511:
  0- 63   64-127  128-191  192-255  256-319  320-383  384-447  448-511
   0      mixed      1        1      mixed      0        0        0

64-127:
 64- 71   72- 79   80- 87   88- 95   96-103  104-111  112-119  120-127
   0        0        0        0      mixed      1        1        1

96-103:
 96   97   98   99  100  101  102  103
  0    0    0    0    1    1    1    1

256-319:
256-263  264-271  272-279  280-287  288-295  296-303  304-311  312-319
   1        1        1        1        1      mixed      0        0

296-303:
296  297  298  299  300  301  302  303
  1    1    1    1    1    0    0    0

Таким образом, дерево будет содержать эти пять узлов:

- values: 00110000, mixed: 01001000, 2 pointers to sub-nodes  
  - values: 00000111, mixed: 00001000, 1 pointer to sub-node
    - values: 00001111, mixed: 00000000
  - values: 11111000, mixed: 00000100, 1 pointer to sub-node
    - values: 11111000, mixed: 00000000

Точка хранения интервала таким образом заключается в том, что вы можете отменить интервал, не удаляя его фактически. Скажем, вы добавили новый диапазон 200-400; в этом случае вы измените диапазон 256-319 в корневом каталоге node от "смешанного" до "1", не удаляя или не обновляя сами узлы 256-319 и 296-303; эти узлы могут быть сохранены для последующего повторного использования (или отключены и помещены в очередь повторно используемых суб-деревьев или удалены в запрограммированной сборке мусора, когда программа работает на холостом ходу или работает на низкой памяти).

Когда вы просматриваете интервал, вам нужно идти только по дереву по мере необходимости; при поиске, например. 225-275, вы обнаружите, что 192-255 все-присутствует, 256-319 смешанно, 256-263 и 264-271 и 272-279 - все присутствующие, и вы знаете, что ответ верен. Поскольку эти значения будут храниться в виде растровых изображений (один для настоящего/отсутствующего, один для смешанного/сплошного), все значения в node могут быть проверены только с несколькими поразрядными сравнениями.

Повторное использование узлов:

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

В приведенном выше примере, если мы добавим диапазон 0-200, это изменит дерево на:

- values: 11110000, mixed: 00001000, 2 pointers to sub-nodes  
  - (values: 00000111, mixed: 00001000, 1 pointer to sub-node)
    - (values: 00001111, mixed: 00000000)
  - values: 11111000, mixed: 00000100, 1 pointer to sub-node
    - values: 11111000, mixed: 00000000

Второй и третий node теперь содержат устаревшие значения и игнорируются. Если затем удалить диапазон 80-95, значение для диапазона 64-127 в корневом каталоге node будет изменено на смешанное снова, а значение node для диапазона 64-127 будет повторно использовано. Сначала мы устанавливаем все значения в нем на все-присутствующие (поскольку это было предыдущее значение родительского node), а затем мы установили значения для 80-87 и 88-95 для всех отсутствующих. Третий node, для диапазона 96-103 остается непригодным.

- values: 00110000, mixed: 01001000, 2 pointers to sub-nodes  
  - values: 11001111, mixed: 00000000, 1 pointer to sub-node
    - (values: 00001111, mixed: 00000000)
  - values: 11111000, mixed: 00000100, 1 pointer to sub-node
    - values: 11111000, mixed: 00000000

Если мы добавим значение 100, значение для диапазона 96-103 во втором node будет изменено на смешанное снова, а третье node будет обновлено до полного отсутствия (его предыдущее значение во втором node), а затем значение 100 будет установлено:

- values: 00110000, mixed: 01001000, 2 pointers to sub-nodes  
  - values: 11000111, mixed: 00001000, 1 pointer to sub-node
    - values: 00001000, mixed: 00000000
  - values: 11111000, mixed: 00000100, 1 pointer to sub-node
    - values: 11111000, mixed: 00000000

Поначалу может показаться, что эта структура данных использует большое количество пространства для хранения по сравнению с решениями, которые хранят интервалы как пары (начало, конец). Однако рассмотрим (теоретический) наихудший сценарий, где присутствует любое четное число, и все нечетные числа отсутствуют во всем 64-битном диапазоне:

Total range: 0 ~ 18,446,744,073,709,551,615  
Intervals:        9,223,372,036,854,775,808

Структура данных, которая хранит эти пары (начало, конец), будет использовать:

Nodes:            9,223,372,036,854,775,808  
Size of node:                            16 bytes  
TOTAL:          147,573,952,589,676,412,928 bytes

Если структура данных использует узлы, которые связаны с помощью (64-разрядных) указателей, это добавит:

Data:           147,573,952,589,676,412,928 bytes
Pointers:        73,786,976,294,838,206,456 bytes
TOTAL:          221,360,928,884,514,619,384 bytes

N-арное дерево с коэффициентом ветвления 64 (и 16 для последнего уровня, чтобы получить полный диапазон 10 и times; 6 + 1 и times; 4 = 64 бит) будет использовать:

Nodes (branch):         285,942,833,483,841  
Size of branch:                         528 bytes  
Nodes (leaf):        18,014,398,509,481,984  
Size of leaf:                           144 bytes  
TOTAL:            2,745,051,201,444,873,744 bytes

что в 53,76 раза меньше (начальных, конечных) парных структур (или в 80,64 раза меньше, включая указатели).

Расчет проводился со следующим N-арным деревом:

Branch (9 levels):
value: 64-bit map
mixed: 64-bit map
sub-nodes: 64 pointers
TOTAL: 528 bytes

Leaf:
value: 64-bit map
mixed: 64-bit map
sub-nodes: 64 16-bit maps (more efficient than pointing to sub-node)
TOTAL: 144 bytes

Это, конечно, самое худшее сравнение; средний случай будет сильно зависеть от конкретного ввода.

Вот первый пример кода, который я написал для проверки идеи. Узлы имеют коэффициент ветвления 16, так что каждый уровень хранит 4 бита целых чисел, а общие битовые глубины могут быть получены без разных листьев и ветвей. В качестве примера создается дерево глубины 3, представляющее диапазон 4 & times; 4 = 16 бит.

function setBits(pattern, value, mask) {                 // helper function (make inline)
    return (pattern & ~mask) | (value ? mask : 0);
}

function Node(value) { // CONSTRUCTOR
    this.value = value ? 65535 : 0;                      // set all values to 1 or 0
    this.mixed = 0;                                      // set all to non-mixed
    this.sub = null;                                     // no pointer array yet
}

Node.prototype.prepareSub = function(pos, mask, value) {
    if ((this.mixed & mask) == 0) {                      // not mixed, child possibly outdated
        var prev = (this.value & mask) >> pos;
        if (value == prev) return false;                 // child doesn't require setting
        if (!this.sub) this.sub = [];                    // create array of pointers
        if (this.sub[pos]) {
            this.sub[pos].value = prev ? 65535 : 0;      // update child node values
            this.sub[pos].mixed = 0;
        }
        else this.sub[pos] = new Node(prev);             // create new child node
    }
    return true;                                         // child requires setting
}

Node.prototype.set = function(value, a, b, step) {
    var posA = Math.floor(a / step), posB = Math.floor(b / step);
    var maskA = 1 << posA, maskB = 1 << posB;
    a %= step; b %= step;

    if (step == 1) {                                     // node is leaf
        var vMask = (maskB | (maskB - 1)) ^ (maskA - 1); // bits posA to posB inclusive
        this.value = setBits(this.value, value, vMask);
    }
    else if (posA == posB) {                             // only 1 sub-range to be set
        if (a == 0 && b == step - 1)                     // a-b is full sub-range
        {
            this.value = setBits(this.value, value, maskA);
            this.mixed = setBits(this.mixed, 0, maskA);
        }
        else if (this.prepareSub(posA, maskA, value)) {  // child node requires setting
            var solid = this.sub[posA].set(value, a, b, step >> 4);     // recurse
            this.value = setBits(this.value, solid ? value : 0, maskA); // set value
            this.mixed = setBits(this.mixed, solid ? 0 : 1, maskA);     // set mixed
        }
    }
    else {                                               // multiple sub-ranges to set
        var vMask = (maskB - 1) ^ (maskA | (maskA - 1)); // bits between posA and posB
        this.value = setBits(this.value, value, vMask);  // set inbetween values
        this.mixed &= ~vMask;                            // set inbetween to solid
        var solidA = true, solidB = true;
        if (a != 0 && this.prepareSub(posA, maskA, value)) {          // child needs setting
            solidA = this.sub[posA].set(value, a, step - 1, step >> 4);
        }
        if (b != step - 1 && this.prepareSub(posB, maskB, value)) {   // child needs setting
            solidB = this.sub[posB].set(value, 0, b, step >> 4);
        }
        this.value = setBits(this.value, solidA ? value : 0, maskA);  // set value
        this.value = setBits(this.value, solidB ? value : 0, maskB);
        if (solidA) this.mixed &= ~maskA; else this.mixed |= maskA;   // set mixed
        if (solidB) this.mixed &= ~maskB; else this.mixed |= maskB;
    }
    return this.mixed == 0 && this.value == 0 || this.value == 65535; // solid or mixed
}

Node.prototype.check = function(a, b, step) {
    var posA = Math.floor(a / step), posB = Math.floor(b / step);
    var maskA = 1 << posA, maskB = 1 << posB;
    a %= step; b %= step;
    var vMask = (maskB - 1) ^ (maskA | (maskA - 1));     // bits between posA and posB

    if (step == 1) {
        vMask = posA == posB ? maskA : vMask | maskA | maskB;
        return (this.value & vMask) == vMask;
    }
    if (posA == posB) {
        var present = (this.mixed & maskA) ? this.sub[posA].check(a, b, step >> 4) : this.value & maskA;
        return !!present;
    }
    var present = (this.mixed & maskA) ? this.sub[posA].check(a, step - 1, step >> 4) : this.value & maskA;
    if (!present) return false;
    present = (this.mixed & maskB) ? this.sub[posB].check(0, b, step >> 4) : this.value & maskB;
    if (!present) return false;
    return (this.value & vMask) == vMask;
}

function NaryTree(factor, depth) { // CONSTRUCTOR
    this.root = new Node();
    this.step = Math.pow(factor, depth);
}

NaryTree.prototype.addRange = function(a, b) {
    this.root.set(1, a, b, this.step);
}

NaryTree.prototype.delRange = function(a, b) {
    this.root.set(0, a, b, this.step);
}

NaryTree.prototype.hasRange = function(a, b) {
    return this.root.check(a, b, this.step);
}

var intervals = new NaryTree(16, 3);                  // create tree for 16-bit range

// CREATE RANDOM DATA AND RUN TEST
document.write("Created N-ary tree for 16-bit range.<br>Randomly adding/deleting 100000 intervals...");
for (var test = 0; test < 100000; test++) {
    var a = Math.floor(Math.random() * 61440);
    var b = a + Math.floor(Math.random() * 4096);
    if (Math.random() > 0.5) intervals.addRange(a,b);
    else intervals.delRange(a,b);
}
document.write("<br>Checking a few random intervals:<br>");
for (var test = 0; test < 8; test++) {
    var a = Math.floor(Math.random() * 65280);
    var b = a + Math.floor(Math.random() * 256);
    document.write("Tree has interval " + a + "-" + b + " ? " + intervals.hasRange(a,b),".<br>");
}

Ответ 5

Я удивлен, что никто не предложил сегментные деревья в целочисленном домене сохраненных значений. (При использовании в геометрических приложениях, таких как графика в 2d и 3d, они называются quadtrees и octrees соответственно.) Вставка, удаление и поиск будут иметь сложность времени и пространства, пропорциональную количеству бит в (maxval - minval), то есть log_2 (maxval - minval), максимальные и минимальные значения целочисленной области данных.

В двух словах мы кодируем набор целых чисел в [minval, maxval]. A node на самом верхнем уровне 0 представляет весь диапазон. Каждый последующий уровень узлов представляет собой поддиапазоны приблизительного размера (maxval - minval)/2 ^ k. Когда включен node, некоторое подмножество его соответствующих значений является частью представленного набора. Когда это лист, все его значения находятся в наборе. Когда он отсутствует, его нет.

например. если minval = 0 и maxval = 7, то k = 1 дети k = 0 node представляют [0..3] и [4..7]. Их дети на уровне k = 2 являются [0..1] [2..3] [4..5] и [6..7], а k = 3 узлы представляют отдельные элементы. Множество {[1..3], [6..7]} будет деревом (уровни слева направо):

[0..7] -- [0..3] -- [0..1]
       |         |        `-[1] 
       |         `- [2..3]
        ` [4..7]
                 `- [6..7]

Нетрудно видеть, что пространство для дерева будет O (m log (maxval - minval)), где m - количество интервалов, хранящихся в дереве.

Нечасто использовать деревья сегментов с динамической вставкой и удалением, но алгоритмы оказываются довольно простыми. Требуется некоторое внимание к тому, чтобы минимизировать количество узлов.

Вот несколько очень легкий Java-код.

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class SegmentTree {
  // Shouldn't differ by more than Long.MAX_VALUE to prevent overflow.
  static final long MIN_VAL = 0;
  static final long MAX_VAL = Long.MAX_VALUE;
  Node root;

  static class Node {
    Node left;
    Node right;
    Node(Node left, Node right) {
      this.left = left;
      this.right = right;
    }
  }

  private static boolean isLeaf(Node node) {
    return node != null && node.left == null && node.right == null;
  }

  private static Node reset(Node node, Node left, Node right) {
    if (node == null) {
      return new Node(left, right);
    }
    node.left = left;
    node.right = right;
    return node;
  }

  /**
   * Accept an arbitrary subtree rooted at a node representing a subset S of the range [lo,hi] and
   * transform it into a subtree representing S + [a,b]. It assumed a >= lo and b <= hi.
   */
  private static Node add(Node node, long lo, long hi, long a, long b) {
    // If the range is empty, the interval tree is always null.
    if (lo > hi) return null;
    // If this is a leaf or insertion is outside the range, there no change.
    if (isLeaf(node) || a > b || b < lo || a > hi) return node;
    // If insertion fills the range, return a leaf.
    if (a == lo && b == hi) return reset(node, null, null);
    // Insertion doesn't cover the range. Get the children, if any.
    Node left = null, right = null;
    if (node != null) {
      left = node.left;
      right = node.right;
    }
    // Split the range and recur to insert in halves.
    long mid = lo + (hi - lo) / 2;
    left = add(left, lo, mid, a, Math.min(b, mid));
    right = add(right, mid + 1, hi, Math.max(a, mid + 1), b);
    // Build a new node, coallescing to leaf if both children are leaves.
    return isLeaf(left) && isLeaf(right) ? reset(node, null, null) : reset(node, left, right);
  }

  /**
   * Accept an arbitrary subtree rooted at a node representing a subset S of the range [lo,hi] and
   * transform it into a subtree representing range(s) S - [a,b].  It assumed a >= lo and b <= hi.
   */
  private static Node del(Node node, long lo, long hi, long a, long b) {
    // If the tree is null, we can't remove anything, so it still null
    // or if the range is empty, the tree is null.
    if (node == null || lo > hi) return null;
    // If the deletion is outside the range, there no change.
    if (a > b || b < lo || a > hi) return node; 
    // If deletion fills the range, return an empty tree.
    if (a == lo && b == hi) return null;
    // Deletion doesn't fill the range. 
    // Replace a leaf with a tree that has the deleted portion removed. 
    if (isLeaf(node)) {
      return add(add(null, lo, hi, b + 1, hi), lo, hi, lo, a - 1);
    }
    // Not a leaf. Get children, if any.
    Node left = node.left, right = node.right;
    long mid = lo + (hi - lo) / 2;
    // Recur to delete in child ranges.
    left = del(left, lo, mid, a, Math.min(b, mid));
    right = del(right, mid + 1, hi, Math.max(a, mid + 1), b);
    // Build a new node, coallescing to empty tree if both children are empty.
    return left == null && right == null ? null : reset(node, left, right);
  }

  private static class NotContainedException extends Exception {};

  private static void verifyContains(Node node, long lo, long hi, long a, long b)
      throws NotContainedException {
    // If this is a leaf or query is empty, it always contained.
    if (isLeaf(node) || a > b) return;
    // If tree or search range is empty, the query is never contained.
    if (node == null || lo > hi) throw new NotContainedException();
    long mid = lo + (hi - lo) / 2;
    verifyContains(node.left, lo, mid, a, Math.min(b, mid));
    verifyContains(node.right, mid + 1, hi, Math.max(a, mid + 1), b);
  }

  SegmentTree addRange(long a, long b) {
    root = add(root, MIN_VAL, MAX_VAL, Math.max(a, MIN_VAL), Math.min(b, MAX_VAL));
    return this;
  }

  SegmentTree addVal(long a) {
    return addRange(a, a);
  }

  SegmentTree delRange(long a, long b) {
    root = del(root, MIN_VAL, MAX_VAL, Math.max(a, MIN_VAL), Math.min(b, MAX_VAL));
    return this;
  }

  SegmentTree delVal(long a) {
    return delRange(a, a);
  }

  boolean containsVal(long a) {
    return containsRange(a, a);
  }

  boolean containsRange(long a, long b) {
    try {
      verifyContains(root, MIN_VAL, MAX_VAL, Math.max(a, MIN_VAL), Math.min(b, MAX_VAL));
      return true;
    } catch (NotContainedException expected) {
      return false;
    }
  }

  private static final boolean PRINT_SEGS_COALESCED = true;

  /** Gather a list of possibly coalesced segments for printing. */
  private static void gatherSegs(List<Long> segs, Node node, long lo, long hi) {
    if (node == null) {
      return;
    }
    if (node.left == null && node.right == null) {
      if (PRINT_SEGS_COALESCED && !segs.isEmpty() && segs.get(segs.size() - 1) == lo - 1) {
        segs.remove(segs.size() - 1);
      } else {
        segs.add(lo);
      }
      segs.add(hi);
    } else {
      long mid = lo + (hi - lo) / 2;
      gatherSegs(segs, node.left, lo, mid);
      gatherSegs(segs, node.right, mid + 1, hi);
    }
  }

  SegmentTree print() {
    List<Long> segs = new ArrayList<>();
    gatherSegs(segs, root, MIN_VAL, MAX_VAL);
    Iterator<Long> it = segs.iterator();
    while (it.hasNext()) {
      long a = it.next();
      long b = it.next();
      System.out.print("[" + a + "," + b + "]");
    }
    System.out.println();
    return this;
  }

  public static void main(String [] args) {
    SegmentTree tree = new SegmentTree()
        .addRange(0, 4).print()
        .addRange(6, 7).print()
        .delVal(2).print()
        .addVal(5).print()
        .addRange(0,1000).print()
        .addVal(5).print()
        .delRange(22, 777).print();
    System.out.println(tree.containsRange(3, 20));
  }
}