If we keep the dials in a data structure, then to make the solution efficient enough, each update and

query operation will have to run in sub-linear time.

One way to achieve this is to group adjacent dials into buckets containing about

dials each. For

each bucket, we keep track of how many times each digit appears in the bucket. The asymptotic

running time is

and the algorithm can pass in time if carefully implemented.

By using a different data structure, we can reduce the time to O(log N) per query.

Imagine a binary tree in which every leaf represents one dial. Every node in the tree contains 10

numbers – how many times each digit appears in dials contained in the subtree rooted at that node. The

root node of this tree contains information about all the dials. There are about 2·N nodes total.

Consider first how to perform a query in this tree. Given an interval [A, B] we want to count how many

dials in the interval are displaying each digit. We start from the root node and use the following

recursive algorithm:

· If all dials in the subtree of the current node are contained in [A, B], return the 10 numberscontained in this node.
· If the dials [A, B] are entirely contained in the left or right child of the current node, then move to that node (the other node is of no interest).
· Otherwise (some of the dials [A, B] are in the left subtree, and some in the right subtree), recursively query both subtrees and add the results together.

This procedure really splits the query interval into subintervals whose lengths decrease exponentially,

using as large subintervals as possible. The time complexity is O(log N).

To keep the entire tree updated, the update operation would need to be linear, because for example,

when Luka clicks all the dials, the entire tree would need to be updated.

To remedy this, we can use lazy propagation – when an update operation would update the entire

subtree rooted at some node, don't actually do this, but instead increase a "laziness" counter in that

node. When another update or query operation would visit one of the node's children, only then

propagate the counter to the children.

The official source code demonstrates this second approach. The update and query operations are

combined in one function.