Given an array `arr`

of `integers`

of size `n`

. We need to compute the sum of elements from index `i`

to index `j`

. The queries consisting of `i`

and `j`

index values will be executed multiple times.

```
{1, 2, 3, 4, 5}
0 1 2 3 4 indices
query(1, 3) => 2 + 3 + 4 = 9
query(2, 4) => 3 + 4 + 5 = 12
```

```
{5, 6, 7, 8, 9}
0 1 2 3 4 indices
query(1, 3) => 6 + 7 + 8 = 9
query(2, 4) => 12
```

As a follow-up, the interviewer can transition into a light version of System & Design interview:

- How to handle updates in the array?
- How to handle multiple machines? What if data doesn’t fit into one machine?
- What if we need the possibility to add or remove a machine without impacting the others? Or can you redistribute the data?

## Solution

Range sum queries without updates

## Example feedback

Candidates struggle to come up with the optimal approach to this problem. Some of the candidates I asked this question to play around with running sums but fail to see that you have to subtract the upper limit from the lower limit.

## Leave a Reply