I need to store what is essentially an array of N unsigned ints and examine and set them individually as you expect of a simple array. However I also need what I can only describe as a cumulative index on that same data, i.e. "What is the total of all elements from the beginning to element I?" or "At what element does the cumulative total reach threshold X?" The size of the array is determined at compile time and I have a fair amount of discretion over what its actual value is.
I've been musing this for the last couple of days now and I've devised in back-of-an-envelope terms a solution in log N time, although there's still plenty of fine detail to sort through before I have a working solution. However, I have this strong gut feeling that I'm missing something and the same requirements looked at slightly differently suggest a well-known standard structure that I'm simply not seeing.
Does this ring any bells with anyone?