Рассмотрим массив (индекс 0), мне нужно найти сумму отдельных элементов из всех возможных диапазонов[i,n], где 0< i < n

Пример:

arr={1,2,1,3}

sum_range[0,3]={1,2,3}=6
sum_range[1,3]={1,2,3}=6
sum_range[2,3]={1,3}=4
sum_range[3,3]={3}=3  

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

Можно ли решить ее менее чем за O(N^2) времени?

Если кто-то указывает на постоянное дерево сегментов, пожалуйста, объясните или дайте какую-нибудь хорошую ссылку?

Ответы (2)

Это можно сделать за O(n) с помощью простого алгоритма динамического программирования.

Начните с задней части массива и используйте контейнер на основе хэша для хранения уже встречавшихся чисел. Значение последнего элемента, то есть sum_range[n-1], устанавливается в arr[n-1]. После этого значения sum_range[i] должны быть вычислены следующим образом:

  • Если arr[i] не входит в набор видимых чисел, то sum_range[i] = sum_range[i+1]+arr[i]
  • .
  • В противном случае, sum_range[i] = sum_range[i+1]

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

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

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

В коде python3.x, отредактированном после комментария:

array = [1, 2, 1, 3, 5]
диапазон_сумм = 0
общая_сумма = 0
набор значений = набор ()
for val in reversed(array):
    if val not in valueset :
        valueset.add (val)
        диапазон_сумм += val
    общая_сумма += диапазон_сумм

print (total_sum)

2022 WebDevInsider