inception_95's blog

By inception_95, history, 17 months ago, In English,

There is an array of n numbers and after m number of steps, one needs to answer the query. In every step from 1 to m, we calculate the cumulative sum. Then queries are asked, which index contains which number in the array.

For example, if n = 5, m = 3, the array = 2,4,3,9,1

we conduct the m steps.

[2,6,9,18,19]

[2,8,15,33,52]

[2,10,25,58,110]

If the query is 2, the answer will be 25.

Constraints: 1<=n,m<=10^5

How can I solve this problem?

N.B: It just came to my mind. I didn't find any such problem in any OJ. If you can, please provide the link. And sorry for bad english.

 
 
 
 
  • Vote: I like it  
  • -15
  • Vote: I do not like it  

»
17 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I think that this could be useful.