What is the most efficient algorithm to get percentile distribution from histogram distribution?
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.