Some time ago I created a blog post about Sqrt-tree. If you didn't read this post, please do it now.
But earlier, we were able just to answer the queries on a static array. Now we will make our structure more "dynamic" and add update queries there.
So, let's begin!
Consider a query that does the assignment ax = val. We need to perform this query fast enough.
First, let's take a look of what is changed in our tree when a single element changes. Consider a tree node with length l and its arrays: , and . It is easy to see that only elements from and will change (only inside the block with the changed element). will change O(l) elements. Therefore, total update count per node is O(l).
We remember that any element x is present in exactly one tree node at each layer. Root node (layer 0) has length O(n), nodes on layer 1 have length , nodes on layer 2 have length , etc. So the time complexity per update is .
But it's too slow. Can it be done faster?