 # Partial Sums

You are given one array of `numbers` and another one with pairs `(a,b)` representing questions of the type: What is the sum of the numbers between position `a` and `b` in the array? Efficiently compute the answer to the given questions and print them.

Example

Input:

```let numbers = [3, 6, 4, 15, 30]
let queries = [(1,3),(0,4)]

Expected value/output:

``````25
58
``````

[collapse]
Hint

You can either compute the result for each query, which would be inefficient. Or you can use an array to store the following sums:

sum = 0 sum = numbers sum = numbers + numbers sum = numbers + numbers + numbers …

This precomputed data structure will allow you to answer the queries efficiently. For instance sum(1,3) = sum – sum. This operation has O(1) complexity.

[collapse]
Solution

```let numbers = [3, 6, 4, 15, 30]
let queries = [(1,3),(0,4)]
var sums: [Int] = []

func query(a:Int, b:Int) -> Int {
return sums[b+1] - sums[a]
}

func initializeSums() {
sums.append(0)
for i in 0..<numbers.count {
sums.append(sums.last! + numbers[i])
}
}

for queryPair in queries {
print(query(a:queryPair.0, b:queryPair.1))
}
}

func partialSums() {
initializeSums()     (No Ratings Yet) Loading...