Что такое рекуррентное соотношение на практики для баяниста Kycb23⁠⁠

Хочу выразить благодарность Kycb23, хороший человек, но глупый

Для языка С++, но это алгоритм и его можно приспособить под разные языки.

И так дан массив vector <int > U = {2,3,4,5,6,67,7,7576,45,765,75,7,6};

Сама формула выглядит так, но для баяниста Kycb23 она будет непонятная....

b0 = 0

bi+1 = bi +ai

, где i > 0

Из рекуррентной формулы сразу становится ясно, как посчитать массив префиксных сумм за O(n):

vector <int > findPrefixSums ( const vector <int >& U)

{

int n = U . size () ;

vector <int > prefixSums (n + 1, 0) ;

for ( int i = 0; i < n; i ++)

{

prefixSums [i + 1] = prefixSums [i] + U [i ];

}

return prefixSums ;

}

Короче, эта функция позволяет посчитать, допусти сумму от 1 по 4 элемент = [1,4]

Сумма будет 14, можно наивно решать, как баянист Kycb23, но я то хочу, что бы он поумнел, что навряд ли, научить его посложней вещам.