Hello All,

I will be receiving a sequence of numbers a_1,a_2,.....a_n (n ~ million). However, I am given one at a time. Now define

s_t = sum_i(a_i), i = floor(t/2),...,t.

At each round 't', the user inputs a_t, and I output s_t.

This can be easily computed with a space complexity O(n/2), by storing the last $n/2$ entries.

I am wondering if there is a constant space algorithm for this -- that is, I can store some quantities like s_t,s_{t-1},a_t, etc, but it should be a fixed number independent of n.

Please help me with this. I could not think of any, and I suspect it doesn't exist, but I have no proof.

Thank you,
mnssk.