# Optimal Prefix Free Codes with Partial Sorting +
## 2 Solution
### Partial Sum Deferred Data Structure  
Given a multiset \(W[1..n]\) of size \(n\) on an alphabet \([1..\sigma]\) of size \(\sigma\), [PERSON] et al. [23] defined the first deferred data structure supporting for all \(x\in[1..\sigma]\) and \(r\in[1..n]\) queries such as \(\text{rank}(x)\), the number of elements which are strictly smaller than \(x\) in \(W\); and \(\text{select}(r)\), the value of the \(r\)-th smallest value (counted with multiplicity) in \(W\). Their data structure supports \(q\) queries in time within \(O(n(1+\log q)+q\log n)\), all in the comparison model ([PERSON] et al. 's result [23] is actually better than this formula when the number of queries \(q\) is larger than the size \(n\) of the multiset, but such configuration does not occur in the case of the computation of an optimal prefix free code, where the number \(q\) of queries is always smaller or equal to \(n\): for simplicity, we summarize their result as \(O(n(1+\log q)+q\log n))\). To achieve this results, it partially sorts its data in order to minimize the computational cost of future queries, but avoids sorting all of the data if the set of queries does not require it: the queries have then become operators in some sense (they modify the data representation). Note that whereas the running time of each individual query depends on the state of the data representation, the answer to each query is itself independent of the state of the data representation. [PERSON] et al. 's data structure [23] supports only rank and select queries in the comparison model, whereas the computation of optimal prefix free codes requires to sum pairs of weights from the input, and the algorithm that we propose in Section 2.3 requires to sum weights from a range in the input. Such requirement can be reduced to partialSum queries. Whereas partialSum queries have been defined in the literature based on the positions in the input array, we define such queries here in a way that depends only on the content of the multiset (as opposed to a definition depending on the order in which the multiset is given in the input), so that it can be generalized to deferred data structures. **Definition 2** (Partial sum data structure). : _Given \(n\) unsorted positive weights \(W[1..n]\), a partial sum data structure supports the following queries:_  
* \(\text{rank}(x)\)_, the number of elements which are strictly smaller than_ \(x\) _in_ \(W\)_;_
* \(\text{select}(r)\)_, the value of the_ \(r\)_-th smallest value (counted with multiplicity) in_ \(W\)_;_
* \(\text{partialSum}(r)\)_, the sum of the_ \(r\) _smallest elements (counted with multiplicity) in_ \(W\)_._  
**Example 5**. : _Given the array \(A= \begin{bmatrix}5&3&1&5&2&4&6&7\end{bmatrix} \)_  
* _the number of elements strictly smaller than_ \(5\) _is_ \(\text{rank}(5)\!=\!4\)_,_
* _the sixth smallest value is_ \(\text{select}(6)\!=\!5\) _(counting with redundancies), and_
* _the sum of the two smallest elements is_ \(\text{partialSum}(2)\!=\!3\)_._  
We describe below how to extend [PERSON] et al. 's deferred data structure [23], which already supports rank and select queries on multisets, in order to add the support for partialSum queries, with  
Figure 2: Illustrations for the instance based on the text \(T=\) “aaaaaaabc\(\_\_\) –, maximizing the number of occurrences of “EI” in its EI signature \(\mathcal{S}(T)=\) “E El El El”. The columns of the array respectively list the messages, their numbers of occurrences and the code lengths assigned to each. an amortized running time within a constant factor of the asymptotic time of the original solution. Note that the operations performed by the data structure are not any more within the comparison model, but rather in the algebraic decision tree computational model, as they introduce algebraic operations (additions) on the elements of the multiset. The result is a direct extension of [PERSON] et al.