# co.combinatorics: algorithmic combinatorial discrete problem (deferred update?) We are given a sequence $$b_1, b_2, ldots, b_h$$ container, where each container initially contains $$1$$ ball. Sequentially, at each time step $$t = 1, ldots, n$$, a ball is thrown into a adversarially selected compartment $$b_ {j (t)}$$, and we are informed about the bin index $$j (t)$$. Assuming that each container is a set, we denote by $$| b_i |$$ the number of balls contained in the container $$b_i$$.

They also give us a series of integers $$A (i)$$ for $$i in {1, 2, ldots, h }$$, and we assume to have access to each record of $$A ( cdot)$$ as well as read and modify it in constant time. In time $$0$$ each integer $$A (i)$$ is equal to $$i$$.

Our goal is to maintain overtime $$A ( cdot)$$so that for everyone $$i in {1, 2, ldots, h }$$, at every step of time we have that $$A (i)$$ is equal to $$sum_ {k = 1} ^ i | b_k |$$ up to a constant factor (even a logarithmic factor in $$n$$ or $$h$$ It would be acceptable).

Question: How can we build an algorithmic (possibly randomized) strategy to maintain overtime the array of integers $$A ( cdot)$$ with a total (expected if randomized) number of elementary operations (i.e. algorithmic time complexity) equal to $$mathcal {O} (n log n)$$ (or, if possible, $$mathcal {O} (n)$$) while the above restriction is met? 