svineet's blog

By svineet, history, 5 months ago, In English,

Hi,

Problem
My solution

I made a segment tree with a slight modification to the merge function from merge sort. The recurrence should come to:

T(n) = 2T(n / 2) + O(n)

Which should be O(n lg n), for the initial building part. For each query it would take O(lg n) right? Why is this timing out? I made a huge test case and it kept running for like a minute. I tried fast i/o, tried to store results and output later, and converted the vector to list but nothing worked.

Is my analysis wrong? How do I make it faster? Please help.

 
 
 
 
  • Vote: I like it  
  • -4
  • Vote: I do not like it  

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

I feel like your query_tree() works in O(n) 'cause of combine function called.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ahh, I see now. Thank you. I just learnt about Mo's algorithm and solved the problem with it, but I'd like to know how to solve it with persistent segment trees. Do you have any idea?

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

when you combine the tree,from top to the last subtree that exactly be the seg you need, the step you take seems logn, but the you are combine all the way,so when you count the list's size,ie.for every query,the complex may over O(logn).most tools in STL seems slower than plain array or plain code, so the importance is not using list or vector, but the algorithm. for this problem i recommend two solution: 1.Persistent Data Structures,it can very easily solve this problem 2.BIT tree + sort, count every query offline