Каков наилучший алгоритм для нахождения суммы всех элементов в произвольном подмассиве?

Question

У меня есть проблема, и решение ОК-иш. Я надеюсь, что есть лучшее решение.

Проблема

У меня есть массив с около 200 000 целых чисел. Учитывая два индекса, i1 и i2, мне нужно вычислить сумму всех элементов между i1 и i2. Каждое целое число в массиве составляет от 1 до 4 включительно. Например:

a = [1, 3, 2, 4, 3, 2, 4, 1];
subsection_sum(a, 0, 3); // returns 6: (1 + 3 + 2)

Эта операция будет выполнена около 200 000 раз, поэтому должна быть довольно быстрой. Простой счетчик в цикле for - это O (n), и он слишком медленный. Массив никогда не изменяется после построения, поэтому нормально иметь относительно дорогую стадию предварительной обработки.

Мое лучшее решение на данный момент

Этот алгоритм работает за O (log n):

Сначала добавьте в исходный массив нули, пока его длина не станет степенью двойки. Затем разделите массив на две равные части и сохраните сумму каждой. Затем разбейте массив на четверти и сохраните сумму каждого. Затем восьмые. Продолжайте делать это, пока массив не разделится на секции длиной 2 элемента. Для вышеприведенного массива из 8 элементов это выполняется в два этапа:

halves = [(a[0] + a[1] + a[2] + a[3]), (a[4] + a[5] + a[6] + a[7])]
quarters = [(a[0] + a[1]), (a[2] + a[3]), (a[4] + a[5]), (a[6] + a[7])]

Тогда с учетом двух индексов теперь можно вырабатывать сумму subsection_sum за O (log n). Например, subsection_sum (a, 2, 7) == четверти [1] + половинки [1].

Answer 1

Введите вспомогательный массив, который содержит накопленную сумму.То есть элемент i вспомогательного массива имеет сумму элементов от 0 до i исходного массива.В этом случае сумма подмассива - это всего лишь отличие двух элементов от вспомогательного массива.Это даст результат в постоянном времени, O(1).

Это зависит от инварианта в функции subsection_sum, приведенной в вопросе:

subsection_sum(a, 0, i2) = subsection_sum(a, 0, i1) + subsection_sum(a, i1, i2)

, где я предполагаюi1 <= i2.Переупорядочив, мы имеем:

subsection_sum(a, i1, i2) = subsection_sum(a, 0, i2) - subsection_sum(a, 0, i1)

Обратите внимание, что суммы с правой стороны обе начинаются с 0.Вспомогательный массив можно рассматривать как кэширующий значения для сумм от нуля, subsection_sum(a, 0, i), для всех i.

Answer 2

Если вы можете предоставить O(n) дополнительное хранилище, вы можете создать справочную таблицу, чей i -й элемент является суммой элементов с индексами от 0 до i (включительно) во входном массиве. В псевдокоде:

def computeLookupTable(arr):
    let n = arr.length
    let lookupTable = new Array()

    lookupTable[0] = arr[0]

    for i=1 to n:
        lookupTable[i] = arr[i] + lookupTable[i-1]

    return lookupTable

Затем вы можете использовать эту таблицу, чтобы вычислить сумму всех элементов в array между i1 и i2, взяв разницу

lookupTable[i2] - lookupTable[i1]

, что занимает постоянное время.