What is the most efficient algorithm to get percentile distribution from histogram distribution? So let's say you have a histogram distribution represented as an array where each element is equal to the number of numbers from the underlying data set that are equal to that element's index.

For example, if your underlying data had 5 0's, 18 1's, 11 2's, 0 3's, etc., then the array representing this distribution would look like...
histogramBinSizes = [5, 18, 11, 0, ...]

Now, let's say you want to get the percentile distribution, which would be represented as an array where each element is equal to the number of numbers from the underlying data that fall in that percentile. What's the most efficient algorithm to get the percentile distribution array? (Maybe call this array percentileBinSizes)

To make the question easier, assume the numbers in the underlying data range from 0 to 100. That would make it so that histogramBinSizes and percentileBinSizes both have lengths of 101. Is there an even more efficient algorithm when this constraint is added?

I tagged this question with data structures as well as algorithms because I'm open to solutions that use a different data structure besides arrays. However, the input and output should still be arrays.
First, compute the cumulative distribution.  Suppose the input array is $A[0..n-1]$.  You can compute the cumulative distribution as follows:


Set $C[-1] := 0$.
For $i:=0,1,2,\dots,n-1$, do: set $C[i] := C[i-1] + A[i]$.


After this, $C[i]$ contains a count of the number of values in the underlying data set that are $\le i$.

Now you can compute percentiles directly from the cumulative distribution.  In particular, item $i$ is in the $\lfloor 100 C[i] / C[n-1] \rfloor$ percentile.  So, the output array can be computed as


Set $P[j] := 0$ for $j=:0,1,2,\dots,100$.
For $i:=0,1,\dots,n-1$, do:


Set $j := \lfloor 100 C[i] / C[n-1] \rfloor$, and set $P[j] := P[j] + A[i]$.



Now $P[j]$ contains the number of values from the underlying data set that fall into the $j$th percentile.  That was what you wanted to compute.

The running time is $O(n)$, where $n$ is the length of the input array.  It seems unlikely you can build anything that's any faster than that, as the problem seems to require reading the entire input.