Uknown Data Structure — (Sqrt Fragmented Tree)

Revision en3, by cjtoribio, 2016-08-30 07:59:26

I was trying to solve this problem from the gym and I struggled to find the solution. Finally I came up with a very interesting data structure capable of handling any subtree update and really don't know if someone else has seen it before, but I will post it here since I could find its name (if it has) in google. My solution was able to solve the problem with O(N) memory, O(N) in creation, O(sqrt(N)) per query. When I saw the editorial I saw that it had another interesting approach with an update buffer which solved the problem in O(Q*sqrt(Q)*log(N)), for my surprise my solution was O(Q*sqrt(N) + N) summing the creation and queries, and I saw conveniently Q was 10^4 so probably the author didn't knew about my approach.

Tags #trees, fragmented_tree, decomposition, sqrt_decomposition

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en27 English cjtoribio 2016-08-31 14:00:03 469
en26 English cjtoribio 2016-08-31 01:07:19 1 Tiny change: 'sed $Q <= $10^4$ so p' -> 'sed $Q <= 10^4$ so p'
en25 English cjtoribio 2016-08-30 23:08:54 23
en24 English cjtoribio 2016-08-30 23:03:30 11
en23 English cjtoribio 2016-08-30 23:00:38 3 Tiny change: 'sqrt{Q}log[2]{N})$, for' -> 'sqrt{Q}log{N})$, for'
en22 English cjtoribio 2016-08-30 22:57:10 4 (published)
en21 English cjtoribio 2016-08-30 22:54:23 218
en20 English cjtoribio 2016-08-30 22:37:33 75 Tiny change: 'lem with `O(N)` memory, ' - (saved to drafts)
en19 English cjtoribio 2016-08-30 21:57:46 4 Tiny change: 'formal prove, I am ope' -> 'formal proof, I am ope'
en18 English cjtoribio 2016-08-30 21:56:49 640
en17 English cjtoribio 2016-08-30 21:32:50 95
en16 English cjtoribio 2016-08-30 20:04:11 3 Tiny change: ' and counting how many ' -> ' and count how many '
en15 English cjtoribio 2016-08-30 19:44:33 3 Tiny change: 'ably have abhorred with t' -> 'ably have bored with t'
en14 English cjtoribio 2016-08-30 19:44:08 26 grammar errors fixes
en13 English cjtoribio 2016-08-30 19:27:11 1
en12 English cjtoribio 2016-08-30 17:21:14 88
en11 English cjtoribio 2016-08-30 17:20:32 277 Set headings, add note about similar decomposition
en10 English cjtoribio 2016-08-30 13:08:26 10
en9 English cjtoribio 2016-08-30 13:07:13 4
en8 English cjtoribio 2016-08-30 11:54:16 14 (published)
en7 English cjtoribio 2016-08-30 11:51:41 44
en6 English cjtoribio 2016-08-30 11:49:50 124
en5 English cjtoribio 2016-08-30 11:48:22 3775
en4 English cjtoribio 2016-08-30 09:21:31 5675
en3 English cjtoribio 2016-08-30 07:59:26 741
en2 English cjtoribio 2016-08-30 07:53:06 12 Tiny change: ' to solve this[problem:100589A] problem' -> ' to solve [problem:12A] problem'
en1 English cjtoribio 2016-08-30 07:52:34 97 Initial revision (saved to drafts)