Tree Queries Questions

Revision en1, by dx24816, 2019-12-22 04:46:32

Hello,

I was trying to upsolve this problem (https://codeforces.net/problemset/problem/1254/D), but I don't understand the n sqrt n solution described here (https://codeforces.net/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.net/blog/entry/71534?#comment-559225), can someone explain to me how this works, or how I'm misunderstanding this.

-dx24816

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English dx24816 2019-12-22 04:46:32 557 Initial revision (published)