Tenho um vetor A de tamanho n. Tenho que calcular a soma parcial de cada elemento e escrever na matriz B[i,j].
O pseudo-código mostra uma solução O(n^2);
For i = 1, 2, . . . , n
For j = i + 1, i + 2, . . . , n
B[i, j] <- A[i] + A[i+1] + ... + A[j];
Endfor
Endfor
Existe uma solução O(n) ou O(log n)? Como seria?