Define sum[i] as the sum from index=0 to index=i, you can find the sum between index=i to index=j using sum[j] - sum[i - 1]. Take care of the boundary value !