Структура данных для динамически изменяющейся последовательности n-длины с запросом на длинную длину подпоследовательности

Ответ 1

Это решает проблему только для смежных интервалов. Он не решает произвольных подпоследовательностей.: - (

Это можно реализовать со временем O(1) для интервала и O(log(n)) для change.

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

Далее нам понадобится куча информации для каждого из наших слотов n.

value: Current value in this slot
interval_start: Where the interval containing this point starts
interval_end: Where the interval containing this point ends
heap_index: Where to find this interval in the heap NOTE: Heap operations MUST maintain this!

И теперь умный трюк! Мы всегда сохраняем значение для каждого слота. Но мы только сохраняем информацию интервала для интервала в точке интервала, индекс которого делится на максимальную мощность 2. Для любого интервала всегда есть только одна такая точка, поэтому сохранение/изменение этого очень мало работы.

Затем, чтобы выяснить, в каком интервалах в данный момент попадает данная позиция в массиве, мы должны посмотреть на всех соседей, которые увеличивают полномочия 2, пока не найдем последний с нашим значением. Так, например, информация о местоположении 13 может быть найдена в любой из позиций 0, 8, 12, 13, 14, 16, 32, 64, .... (И мы возьмем первый интервал, который мы найдем в списке 0, ..., 64, 32, 16, 8, 12, 14, 13.) Это поиск O(log(n)), так что O(log(n)) работает.

Теперь, как мы реализуем change?

• Обновить значение.
• Выясните, в каком промежутке мы были, и находились ли мы на границе интервала.
• Если интервалы изменены, удалите старые из кучи. (Мы можем удалить 0, 1 или 2)
• Если интервалы изменились, вставьте новые в кучу. (Мы можем вставить 0, 1 или 2)

Это обновление очень сложно, но это фиксированное число операций O(log(n)) и поэтому должно быть O(log(n)).

Ответ 2

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

class LIS {
    private vector<int> seq ;
    public LIS(vector<int> _seq) {seq = _seq ;}
    public int increasing() {
        int i, j ;
        vector<int> lengths ;
        lengths.resize(seq.size()) ;
        for(i=0;i<seq.size();i++) lengths[i] = 1 ;

        for(i=1;i<seq.size();i++) {
            for(j=0;j<i;j++) {
                if( seq[i] > seq[j] && lengths[i] < lengths[j]+1 ) {
                    lengths[i] = lengths[j] + 1 ;
                }
            }
        }

        int mxx = 0 ;
        for(i=0;i<seq.size();i++)
            mxx = mxx < lengths[i] ? lengths[i] : mxx ;

        return mxx ;
    }

    public void change(i, x) {
        seq[i] += x ;
    }

}

Ответ 3

Я пытаюсь объяснить свою идею. Это может быть немного проще, чем внедрять дерево интервалов, и должно дать желательную сложность - O (1) для увеличения() и O (logS) для change(), где S - количество последовательностей (в худших случаях может быть уменьшено до N конечно).

Сначала вам нужен оригинальный массив. Он должен проверить границы интервалов (я буду использовать интервал слов как синоним последовательности) после change(). Пусть это будет A

Во втором вам нужен двунаправленный список интервалов. Элемент этого списка должен хранить левую и правую границы. Каждая возрастающая последовательность должна быть представлена ​​как отдельный элемент этого списка, и эти интервалы должны идти один за другим, поскольку они представлены в A. Пусть этот список L. Нам нужно управлять указателями на элементах, поэтому я не знаю, возможно ли это сделать на итераторах со стандартным контейнером.

В третьих вам нужна очередь приоритетов, в которой хранятся длины всех интервалов в вашем массиве. Таким образом, функция увеличения() может быть выполнена с O (1) временем. Но вам нужно также сохранить указатель на node от L до интервалов поиска. Пусть эта очередь приоритетов PQ. Более формально ваша очередь приоритета содержит пары (длина интервала, указатель на список node) при сравнении только по длине.

Вперёд вам нужно дерево, которое может извлекать интервальные границы (или диапазон) для определенного элемента. Он может быть просто реализован с помощью std:: map, где ключ остается левой границей дерева, поэтому с помощью map:: lower_bound вы можете найти этот интервал. Значение должно хранить указатель на интервал в L. Пусть это отображение MP

И следующая важная вещь: узлы списка должны хранить отдельные элементы соответствующего элемента в очереди приоритетов. И вы не должны работать с очередью приоритетов без подключения со ссылкой на node от L (каждая операция подкачки на PQ вам следует обновить соответствующие индексы на L).

change (i, x) может выглядеть так:

• Найдите интервал, где я расположен с картой. → вы найдете указатель на соответствующий node в L. Итак, вы знаете границы и длину интервала
• Попробуйте понять, какие действия нужно делать: ничего, интервалы между интервалами, интервалы клеев.
• Сделайте это действие в списке и сопоставьте с подключением с PQ. Если вам нужен интервал разделения, удалите его из PQ (это не операция remove-max), а затем добавьте 2 новых элемента в PQ. Аналогично, если вам нужно слить интервалы, вы можете удалить один из PQ и сделать увеличение до второго.

Одна из трудностей заключается в том, что PQ должен поддерживать удаление произвольного элемента (по индексу), поэтому вы не можете использовать std:: priority_queue, но это не сложно реализовать, как я думаю.