Diseñe un algoritmo rápido para generar repetidamente números a partir de la distribución discreta: dada una matriz a [] de números reales no negativos que suman 1, el objetivo es devolver el índice i con probabilidad a [i]

Encontré esta pregunta en un libro de algoritmos en línea, Introducción a la programación en Java, capítulo 4.2: Clasificación y búsqueda (http://introcs.cs.princeton.edu/java/42sort/).

la pista dice:

Forme una matriz s [] de sumas acumuladas de manera que s [i] sea la suma de los primeros elementos i de a []. Ahora, genere un número real aleatorio r entre 0 y 1, y use la búsqueda binaria para devolver el índice i para el que s [i] ≤ s [i + 1].

De alguna manera, no puedo entender la sugerencia y, por lo tanto, no puedo encontrar la solución.