About that problem - why did you say O((log n)^2)?
There's an algorythm with O(log n) for both request and update, and
it was quite easy for me to find it. I suggested to find the
O(n*Sqrt(n)) algorythm because for me it seems to be a bit easier to
implement - anyway, I use it in problems of these kind - it works
quite fast.

Well, I've thought about it a bit more, and yes, I've thought of the O
(log n) method.  The O((log n)^2) was thought off the top of my head
immediately after I saw the question.

Thanks for your information anyway.