FineLine's blog

HELP REQUIRED IN SPOJ K-QUERY
By FineLine, history, 10 years ago, In English

Hi everyone,I have been trying this question SPOJ K-QUERYfor 2 days now.After unsuccessful attempts to come up with logic,I finally referred Blogs available online.But I am neither getting head nor tail of the logic. Can someone please tell me the formation of fenwick/segment tree that is used(especially the technique used).It will be a great help.Please! Thanks in advance.

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

Comments Comments (5)
| Write comment?
»
10 years ago, hide # |
← Rev. 3  
Vote: I like it +3 Vote: I do not like it

try amd blog on segment tree he has explained it nicely segment tree. If you still need help then ask.

→ Reply
»
10 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

That has been explained so many times... Just google it.

→ Reply
  • »
    »
    10 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    I had tried it.But I did not get good explanation .All the blogs gave code .I tried understanding it using pen and paper literally.But I could not get the basic strategy behind it.The best blog I got was of PrinceOfPersia , But still could not understand it. Instead of showing me How to Google ,It would have been great that you could have explained it to me. Anyways Thanks radoslav11....

    → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
       
      Vote: I like it +11 Vote: I do not like it

      Well the main idea is to solve the problem offline. At every query we should care just for elements with value < K. Lets make events. Every event will be either an adding of element at position POS with value VAL or a query.

      We sort these events by VAL and K (depends if event is an adding or a query). Then our problem becomes:

      For every query what is the number of added elements before it in range [L; R].

      This can be done with an range-query and point update on segment tree or with a BIT: For every adding we set the value of POS with 1 and for every query we get sum of [L; R].

      The complexity is O(Nlog(N) + (M+N)*log(N)) = O(Nlog(N)).

      PS: The problem can be also solved online with a merge sort tree in O(N*log^2(N)) time.

      → Reply
      • »
        »
        »
        »
        10 years ago, hide # ^ |
         
        Vote: I like it +11 Vote: I do not like it

        Thanks radoslav11 and SORRY if you found my above comment offensive .I actually had tried lot before asking on the forum.Again Sorry!!

        → Reply