How can I efficiently compute the sum of parts of an array of sizes in an arithmetic sequence?

I am trying to find the sum of parts of a given array with a length that is the sum of the first N positive integers for some whole number N. The size of each part for which I am to find the sum are the numbers in said arithmetic sequence. For instance, for an array of length 10, I need to find the sum of the first number, the next two numbers, and so on, until the next N numbers.

Example Input:

[1,4,5,2,6,7,9,8,7,10]

Example Output:

[1,9,15,34]//1, 4+5, 2+6+7, 9+8+7+10

Explanation:

The first sum is 1, the first element (index 0). The sum of the next two numbers is 4 + 5 = 9 (index 1 and 2). The sum of the next three numbers is 2 + 6 + 7 = 15 (index 3, 4, and 5). The sum of the last four numbers is 9 + 8 + 7 + 10 = 34 (index 6, 7, 8, 9).

You can compute the size of the result array using the formula for the sum of an arithmetic sequence, i.e. n(n + 1) / 2.

A prefix sum array can be applied here so so that any range sum can be computed in O(1) time with O(n) precomputation time and space (which is also the overall complexity of this algorithm).

final int[] input = { 1, 4, 5, 2, 6, 7, 9, 8, 7, 10 };
// size * (size + 1) / 2 = input.length
final int size = (-1 + (int) Math.sqrt(1 + 8 * input.length)) / 2;
// derived by quadratic formula
final int[] result = new int[size];
final int[] sum = new int[input.length + 1];
for (int i = 1; i <= input.length; i++) {
    sum[i] = sum[i - 1] + input[i - 1];
}
for (int i = 1, j = 0; i <= input.length; i += ++j) {
    result[j] = sum[i + j] - sum[i - 1];
}
System.out.println(Arrays.toString(result));

<kbd>Ideone Demo</kbd>

The following algorithm is very efficient and does not rely on the summation formula to work (as you had asked about) other than to compute the length of the result array. This should not be a problem since it is basic algebra. If you use a List implementation you would not have to do that.

It also only sums only to the max allowed by the given array. So if you provide an array like

1 2 3 4 5 6 7 8 9 10 11 12 13

It will silently ignore 11 12 and 13 since they don't comprise enough values to continue.

Here is the algorithm with your original data set and the output.

		
int[] arr = { 1, 4, 5, 2, 6, 7, 9, 8, 7, 10 };

int start = 0; // start of group
int end = 0; // end of group
int[] sol = new int[(int)(-.5 + Math.sqrt(2*arr.length + .25))];
for (int i = 1; i <= sol.length; i++) {
    // initialize the sum
	int sum = 0;
    // compute next end
	end += i;
    // and sum from start to end
	for (int k = start; k < end; k++) {
		sum += arr[k];
	}
    // old end becomes next start
	start = end;

    sol[i-1] = sum;
}

Prints

[1, 9, 15, 34]


</details>