Task 106. Частичная сумма
UniLecsЗадача: дан массив чисел arr = [a1, a2, ..., an]. Есть набор индексов (k, r).
Необходимо вычислить частичную сумму в массиве:
S(k, r) = a(k) + a(k+1) + a(k+2) + ... + a(r).
Входные данные: arr - массив действительных чисел от 1 до 10^6.
indexArr = [(k1, r1), (k2, r2), ... ] - массив индексов (k, r). Размер массива indexArr от 1 до 10^6. Индексы ki, ri - натуральные числа от 1 до 10^6 и ki <= ri.
Вывод: вывести значения частичных сумм S(ki, ri) для заданного набора индексов.
Пример: arr = [1, 2, 3, 4, 5]; indexArr = [(1, 5), (2, 3), (3, 4)]
Answer: 15 5 7
Идея: из за большой размерности входных массивов решать задачу в лоб довольно затратно и не оптимально, поэтому воспользуемся частичными суммами массива.
Получаем:
S(1, 1) = a1
S(1, 2) = a1 + a2
S(1, 3) = a1 + a2 + a3
...
S(1, n) = a1 + a2 + a3 + ... an
Можно заметить, что частичную сумму можно выразить след.формулой:
S(k, r) = a(k) + a(k+1) + ... + a(r) = (a1 + a2 + ... + a(k) + a(k+1) + ... a(r)) - (a1 + a2 + ... + a(k-1)) = S(r) - S(k-1)
Теперь для решения исходной задачи нам достаточно только сформировать массив частичных сумм, а само значение S(k, r) мы находим за константное время O(1).
Реализация:
https://gist.github.com/unilecs/cb8bc240c2bb139e5d931be2bfe35c7c
Test: