CODEWITHSUNDEEP
algorithmdata-structurestime-complexity
Micro Optimizer
Micro Optimizer

Reputation: 227

Is it possible to get the sum of all contiguous subarrays in O(n) time?

As part of a larger problem I'm solving, I'm curious whether it's possible in linear time to go from 

{a_0, a_1, ..., a_n-1}

to generating a mapping 

f(i,j): sum of elements over range [i,j) for all i,j in {0, 1, ..., n - 1}

e.g. 

{ 5, 1, 89, 0 }

----> 

f(0,1) = 5
f(0,2) = 5 + 1 = 6
f(0,3) = 5 + 1 + 89 = 95
f(0,4) = 5 + 1 + 89 + 0 = 95
f(1,2) = 1
f(1,3) = 1 + 89 = 90
f(1,4) = 1 + 89 + 0 = 90
f(2,3) = 89
f(2,4) = 89 + 0 = 89
f(3,4) = 0

Upvotes: 3

Views: 406

Answers (1)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726559

Although you cannot produce an O(n2) amount of data in linear time, you can build a data structure in linear time that would let you compute each of f(x,y) in O(1).

For this you need to build an array s such that si represents a sum of a from zero to i, inclusive of both ends.

You can build an array of partial sums by setting s[0] = a[0] and then setting s[i] = s[i-1] + a[i] for each i above zero.

Having an array of partial sums lets you compute

f(x,y) = s[y] - (x==0 ? 0 : s[x-1])

Upvotes: 4

Related Questions