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

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

Проблема

У меня есть массив примерно из 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])]

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