This problem is a dynamic programing problem. It is not only the problem to add the numbers between a given range but we can say that it is the problem to make a function to compute range sum in o(1) time for each given range otherwise we have to go through the array each time for computing the sum, this will cost one traversal of array each time i.e. o(n) complexity each time. If you are confused with this explanation then sorry for that and please go through this very nice explanation by @jianchao.li.fighter for further details ,