Timeline for On an array of sets, Data structure to handle Interval insert, Interval erase, Interval sum of size query
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 18, 2020 at 10:28 | vote | accept | amirali | ||
| Apr 18, 2020 at 10:06 | comment | added | Antti Röyskö | Yes, as the potential function decreases whenever we recurse down after finding a node whose interval is contained in the query interval. Time complexity of both insertion and deletion is amortised $\mathcal{O}(\log n \log q)$, and queries work in $\mathcal{O}(\log n)$. | |
| Apr 18, 2020 at 10:02 | history | edited | Antti Röyskö | CC BY-SA 4.0 |
add code
|
| Apr 18, 2020 at 8:12 | comment | added | amirali | Correct me if I'm wrong: In insertion and deletion query you recurse to children while the element is available in some[i] and erase the element from all[i]. And you prove that this won't take that much time? And please mention your final time/memory complexity for all of the operations. | |
| Apr 18, 2020 at 6:34 | comment | added | Antti Röyskö | It does, that's why it's $\mathcal{O}(\log n \log q)$ amortised time. Note that in that case we do $\frac{n}{2} + 1$ operations, but in total only $\mathcal{O}(n \log n)$ work. The definition of "amortised $\mathcal{O}(\log n \log q)$ time per operation" is that for sufficiently large $q$, making $q$ operations takes in total at most $\mathcal{O}(q \log n \log q)$ time. | |
| Apr 18, 2020 at 5:52 | comment | added | amirali | Please explain what will your solution do for this test case: First add element 1 to all indices which are even, then erase element 1 from [ 1, n ]. If I understand correctly, your solution takes linear time on erasing query, because element 1 should be erased from sets of lowers vertices. If you don't erase it from lower children, you won't answer sum query correctly. | |
| Apr 18, 2020 at 5:19 | history | answered | Antti Röyskö | CC BY-SA 4.0 |