rm-rf's blog

What would be the intended time complexity of this problem?
By rm-rf, 11 months ago, In English

Hi!

For this problem, the time complexity of my implementation is around O(q * k * log(n)), but it got TLE. So I wonder what would be the intended time complexity for this problem?

Thanks!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think it will be the $$$O(Q\cdot\sqrt{N}+\sum{K})$$$, so it musb be needed $$$O(1)$$$ update each point update and $$$O(\sqrt{N})$$$ in every tree path (IN MY OPINIOON)

→ Reply