Найдите сумму произведения элементов массива в диапазоне [L, R]

Дан массив arr[] и два целых числа L и R . Задача состоит в том, чтобы найти сумму произведения всех пар (i, j) в диапазоне [L, R] таких, что i ≤ j .

Input: arr[] = { 1, 3, 5, 8 }, L = 0, R = 2
Output: 58
Explanation: As 1*1 + 1*3 + 1*5 + 3*3 + 3*5 + 5*5 = 58

Input: arr[] = { 2, 1, 4, 5, 3, 2, 1 }, L = 1, R = 5
Output: 140

Наивный подход: подход грубой силы может быть реализован напрямую путем умножения индексов с использованием двух вложенных циклов и сохранения суммы в переменной.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N ² )
Вспомогательное пространство: O(1)

Эффективный подход: эта проблема может быть эффективно решена с помощью метода суммы префиксов. В этом методе сохраните сумму префикса в предварительном вычислении, а затем повторите один цикл от L до R и умножьте соответствующую сумму префикса от этого индекса до последнего индекса.

Basically 1*1+1*3+1*5+3*3+3*5+5*5 can be written as 1*(1+3+5)+3*(3+5)+5*(5) = 1*(prefix_sum from 1 to 5)+3*(prefix_sum from 3 to 5)+5*(prefix sum from 5 to 5)

Ниже приведена реализация описанного выше подхода.

Временная сложность: НА)
Вспомогательное пространство: O(N)