Cool article buddy. But there’s one more thing.
Your accountant comes up and says Sir, we’ve messed up the data collection for the entire 5th year and 41st year. You say, that’s no biggie, fret not my child for we’ll update the values in the array right away and continue to trod along our merry way.
Right? Wrong. You are royally screwed.

Your prefix sum consists of inconsistent and inappropriate terms. You could however run your prefix sum array creation again, but who’s to say your accountant didn’t screw on the 34th year as well. The problem is, prefix sum cannot handle cases where there are updates in the array, which is often the case in a real world problem. For tackling this, you have to understand Segment trees and/or a simpler Fenwick tree.
What you talk about in the article refers to a range sum query.
Cheers.

Engineering @Flipkart

Engineering @Flipkart