Найти наибольший субарий суммы из данного массива с использованием деревьев сегментов

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

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

Ответ 1

Согласно моему комментарию к ответу Джастина, вы можете увеличить стандартное дерево сегментов, чтобы достичь времени запроса O(log(n)) с O(n log(n)) временем для построения дерева, то есть вставить все n элементов в дерево.

Идея состоит в том, чтобы хранить в каждом node v не только одно значение, но четыре:

max_value [v]: = максимальная непрерывная сумма в поддереве v `

left_value [v]: = максимальная непрерывная сумма, смежная с левой границей диапазона, соответствующей v поддереву

right_value [v]: = максимальная непрерывная сумма, смежная с правой границей диапазона, соответствующая v поддереву

sum [v]: = сумма всех элементов в v поддереве

Чтобы выполнить операцию обновления для node v, вам нужно пересчитать max_value[v], left_value[v], right_value[v], sum[v]. Это очень просто, и я думаю, что вы можете понять это сами - есть несколько случаев, чтобы рассмотреть.

Операция запроса аналогична операции запроса в базовом дереве сегментов. Единственное различие заключается в том, что в этом случае вы должны учитывать также left_value[v] и right_value[v] при вычислении результата - опять же, есть несколько простых случаев для рассмотрения.

Я надеюсь, что вы выясните пропущенные подробности. Если нет, сообщите мне, и я дам более подробное объяснение.

Ответ 2

В то время как ответ @pkacprzak описывает решение хорошо, некоторые люди могут предпочесть пример кода.

#include <iostream>
#define ll long long
using namespace std;
const int N=1<<17; // big power of 2 that fits your data

int n,k;
struct P {ll l, r, ts, bs;}; // left, right, totalsum, bestsum
P p[2*N];

ll maxf(ll a,ll b,ll c) {return max(a,max(b,c));}

P combine(P &cl,P &cr) {
  P node;
  node.ts = cl.ts + cr.ts;
  node.l = maxf(cl.l, cl.ts, cl.ts + cr.l);
  node.r = maxf(cr.r, cr.ts, cr.ts + cl.r);
  node.bs = maxf(cl.bs, cr.bs, cl.r + cr.l);
  return node;
}

void change(int k, ll x) {
  k += N;
  p[k].l = p[k].r = p[k].ts = p[k].bs = x;
  for (k /= 2; k >= 1; k /= 2) {
    p[k] = combine(p[2*k], p[2*k+1]);
  }
}

Чтобы добавить/изменить значения в дереве сегментов, используйте change(k, x) (O(log(n)) за вызов), где k - позиция, а x - значение. Максимальная сумма субарама может быть считана из p[1].bs (вершина дерева) после каждого вызова change.

Если вам также нужно найти точные индексы подмассива, вы можете сделать рекурсивный нисходящий запрос в O(log(n)) или двоичный поиск O(log^2(n)) с итеративным запросом.

EDIT: если нас интересует максимальный подмассив данного подмассива, лучше всего построить рекурсивный запрос сверху вниз. См:

https://www.quora.com/How-do-I-calculate-the-maximum-sub-segment-sum-in-a-segment-tree

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