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?