Hello,

I was trying to upsolve this problem (https://codeforces.com/problemset/problem/1254/D), but I don't understand the n sqrt n solution described here (https://codeforces.com/blog/entry/71594?#comment-559559). Can someone explain in more detail how you can do all the sqrt(q) updates in linear time?

Also, I saw in this comment that binary indexed trees can go to constant time (https://codeforces.com/blog/entry/71534?#comment-559225), can someone explain to me how this works, or how I'm misunderstanding this.

-dx24816