Как найти сумму элементов из заданного индексного интервала (i, j) за постоянное время?

Question

Учитывая массив. Как мы можем найти сумму элементов в интервале индекса (i, j) в постоянном времени. Вам разрешено использовать дополнительное пространство.
Пример:
A: 3 2 4 7 1 -2 8 0 -4 2 1 5 6 -1
длина = 14

int getsum(int* arr, int i, int j, int len);
// suppose int array "arr" is initialized here
int sum = getsum(arr, 2, 5, 14);

сумма должна быть 10 в постоянное время.

Answer 1

Если вы можете потратить O (n) время на «подготовку» вспомогательной информации, на основе которой вы сможете рассчитать суммы в O (1), вы можете легко это сделать.

Подготовка (O(n)):

aux[0] = 0;
foreach i in (1..LENGTH) {
  aux[i] = aux[i-1] + arr[i];
}

Запрос (O (1)), arr пронумерован от 1 до LENGTH:

sum(i,j) = aux[j] - aux[i-1];

Я думаю, что это былнамерение, потому что иначе невозможно: для любого length для вычисления sum(0,length-1) вы должны были отсканировать весь массив;это занимает линейное время, по крайней мере.

Answer 2

Это не может быть сделано в постоянное время, если вы не сохраните информацию.

Вы должны будете сделать что-то вроде специального изменения массива, чтобы хранить для каждого индекса сумму всех значений между началом массива и этим индексом, а затем использовать вычитание диапазона, чтобы получить разницу в суммах. 1005 *

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

Любой алгоритм, который должен сканировать группу элементов в последовательном несортированном списке, будет O (n).

Answer 3

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

Find the sum of the interval, if the array gets changed dynamically.

Если элементы массива изменились, то мы должны пересчитать любую сумму, которую мы сохранили во вспомогательном массиве, как указано в подходе @ Pavel Shved. Повторное вычисление является операцией O (n), и поэтому нам нужно уменьшить сложность до O (nlogn), используя Segment Tree.

http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

Answer 4

Существует три известных алгоритма для запросов на основе диапазона, заданных [l, r]

1.Сегментное дерево: общее время запроса O (NlogN) 2.Fenwick дерево: общее время запроса O (NlogN) 3. Алгоритм Мо (разложение квадратного корня)

Первые два алгоритма могут иметь дело с модификациями в предоставленном вам списке / массиве. Третий алгоритм или алгоритм Мо - это автономный алгоритм, означающий, что все запросы должны быть переданы вам заранее. Изменения в списке / массиве не допускаются в этом алгоритме. Для реализации, выполнения и дальнейшего чтения этого алгоритма вы можете проверить этот Средний блог. Это объясняется с кодом. И очень немногие на самом деле знают об этом методе.

Answer 5

этот вопрос решит O (n ^ 2) время, O (n) пространство или O (n) время, O (n) пространство ..

Теперь наилучшее оптимальное решение в этом случае (т.е. время O (n), O (n)) предположим, что задано [] = {1,3,5,2,6,4,9} если мы создадим массив (sum []), в котором мы сохранили значение суммы индекса 0 для этого конкретного индекса. Как и для массива a [], массив sum будет sum [] = {1,4,9,11, 17,21,30}; как {1,3 + 1,3 + 1 + 5 ......} это занимает O (n) время и O (n) пространство .. когда мы даем индекс, то он напрямую выбирается из массива sum, это означает, что add (i, j) = sum [j] -sum [i-1]; и это занимает O (1) раз и O (1) пробелы ... Итак, эта программа занимает O (n) времени и O (N) пробелов.

int sum [] = new int [l];

    sum[0]=a[0];
    System.out.print(cumsum[0]+" ");
   for(int i=1;i<l;i++)
   {
       sum[i]=sum[i-1]+a[i];
       System.out.print(sum[i]+" ");
   }  

? * Это дает 1,4,9,11,17,21,30 и занимает O (n) времени и O (n) пробелов * /

sum (i, j) = сумма [j] -сумма [i-1] / это дает сумму индексов от i до j и занимает O (1) времени и O (1) пробелов /

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