Обновление максимальной суммы субинтеграла в массиве за сублинейное время при применении смежного преобразования

Question

Я задавал этот вопрос для общих транспозиций, и это казалось слишком сложным, я получил только один ответ, который, казалось, не давал гарантированного асимптотического ускорения. Итак, предположим, что мы применяем последовательность смежных транспозиций к числовому массиву (смежная транспозиция меняет местами два смежных числа), и мы хотим сохранить решение подинтервала максимальной суммы после каждой смежной транспозиции. Мы можем повторить линейное временное решение Кадане с нуля на всем массиве после каждой смежной транспозиции. Вот что я хочу побить. Может ли это быть сделано за сублинейное время для каждой смежной транспонирования, скажем, если мы сделаем N или N^2 смежных транспонирования для массива размера N, и нам разрешено делать предварительную обработку, пока амортизированное время предварительной обработки является сублинейным для всего набора Прикладные транспозиции?

Answer 1

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

Напомним, что алгоритм Кадане поддерживает две величины: max (ака max_so_far), максимальная сумма подмассива, и max_right (ака max_ending_here), максимальная сумма подмассива, простирающегося от правой границы. Двусторонний Kadane вычисляет еще две величины: max_leftмаксимальная сумма подмассива, которая простирается от левой границы, и max_left_right- максимальная сумма подмассива, которая простирается от левой и правой границ (т. е. сумма массива). Сохраните эту информацию в следующей структуре.

struct KadaneResult {
    int max;
    int max_right;
    int max_left;
    int max_left_right;
};

Теперь, учитывая структуры результата для двух массивов, мы можем вычислить структуру результата для их объединения. Доказательство правильности должно быть легким, если ты понимаешь Кадане, а я не облажался:)

KadaneResult Combine(KadaneResult left, KadaneResult right) {
    KadaneResult both;
    both.max = maximum(left.max, right.max, left.max_right + right.max_left);
    both.max_right = maximum(right.max_right, left.max_right + right.max_left_right);
    both.max_left = maximum(left.max_left, left.max_left_right + right.max_left);
    both.max_left_right = left.max_left_right + right.max_left_right;
    return both;
}

Для полноты вычислите структуру результата для нуля и одного элемента.

KadaneResult Zero() {
    KadaneResult zero;
    zero.max = 0;
    zero.max_right = 0;
    zero.max_left = 0;
    zero.max_left_right = 0;
    return zero;
}

KadaneResult One(int x) {
    KadaneResult one;
    one.max = maximum(0, x);
    one.max_right = maximum(0, x);
    one.max_left = maximum(0, x);
    one.max_left_right = x;
    return x;
}

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