Kakashi_150's blog

Hackerearth question on segment tree
By Kakashi_150, history, 6 years ago, In English

Hello all, I have a question from hackerearth which is tagged under segment tree. Can anyone tell me what approach to use to solve it using segment tree? Link

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It could be solved without segment tree also.Refer https://www.hackerearth.com/submission/15779371/

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

Question is saying given an array of N elements, in each query give the number of pairs in [L, R] that have the same number of divisors.

  • The key observation here is that upto a million, the number of factors a number can have is not too large. In fact, it's about a 100.

  • Maintain a 100 segment trees. Each segment tree contains the frequency of divisor i.

  • Suppose you have to replace element x with element y. Then update segment tree d(x) and segment tree d(y).

  • To answer the other query, go over all 100 segment trees. If a pair has frequency f in range [L, R], add to the answer.

Note — I've explained a harder version of the question. In the given question, you only have to answer queries reporting the number of pairs in range [L, R], you don't have to deal with point updates. So, segment tree is unnecessary overhead here and prefix arrays are better. If the question said that in some queries you must replace certain numbers, then you can use segment trees :)

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ok thank you ghoshsai5000 . Here is another problem this time of fenwick tree. Please tell me the logic to solve it. Thanks once again :-) Link

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      lazy propagation + seg tree.try to maintain maximum and minimums in a segment and propagate in the tree. Refer this : https://www.hackerearth.com/submission/17727529/

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If you want a segment tree question from HackerEarth, here's one that I've actually solved.

      Now in the other question you sent.

      Here's what's done ... Maintain the array in such a way that if you sum from [1, i] you will get A[i]. We do this by inserting A[i] at position i and  - A[i] at position (i + 1).

      For each subtraction query, put a  - 1 at A[1] and 1 at x + 1

      For each finding query, perform binary search with the help of the segment tree.

      → Reply