I completely understand this code and what it is accomplishing.

What I struggle with is seeing/finding a solution like this. What is your thought process? Can someone explain how one is supposed to just know to implement a solution like this? Is this just one of those problems where you just say "Hm, this smells like a prefix sum type of problem"? I didn't even know what a prefix sum was until doing this problem xD

I stared at this problem for some time, and I can tell you I would never have figured out this trick to solve the problem.

Any pointers would be much appreciated :D