Mhammad1's blog

Segment Tree Problem!
By Mhammad1, history, 9 years ago, In English

Hello every one

I've solved this problem but I have different questions about this problem:

The link : Frequent Values

The questions:

1 — How can I solve this problem if the values not sorted?

2 — How can I solve this problem online?

3 — How can I solve this problem if the values not sorted and online?

Edit: The link for the first question is here: values not sorted

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

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

First is Mo algorithm ...

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

    Please explain how it can be done by Mo algorithm?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +7 Vote: I do not like it

      So for online method you can use BIT and make a new array b(b[i]=the numers of number from left of i with value a[i]).Now for query [L,R] take maximal from range :)

      If values not sorted ,use Mo's algorithm.Read http://blog.anudeep2011.com/mos-algorithm/ . He has an example where he uses frequencies.U have to make the same but ,let's say we have an element with frequency x stored,we wanna keep an array and put 1 for every i(1<=i<=x).So in general,if you decrease the frequenct of an element from x to x-1,you decrease 1 at position x,if you increase,you increase 1 at position x+1.

      Now for every query you binary search the last element in that array which is >0(hence there is a frequency existent).Or you can remove binary search and keep maximal 1 in the array,and update it when you decrease 1.

      Total complexity O(N*sqrt(n)+Q*sqrt(n)+Q*log(n))) or O((N+Q)*sqrt(n)) The other solution is to keep a seg tree but it takes O(N*sqrt(n)+Q*sqrt(n)*log(n)),worse performane

      For the 3rd problem,I wait myself for a solution...

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

        Thanks for the link and explanation, but I have another question:

        Is every problem solvable by BIT can be solved by Segment Tree?

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          BIT can be used for sum (in every case),and for maximal,minimal element when for a position ,every time you update the element,is better or equal than the previous value.Also can be used for multiplication when element is updated just once.

          Seg tree can be used for a lot more things(gcd,multiplication-every time),lazy propagations,progressions,but it is more inefficient..

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

    can you please provide some problems that needs Mo algorithm.

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

how did you solve this problem??using segment trees??

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

    It's a RMQ problem, you can build the tree of the frequency of every value, so every query can be done by O(log n) , but you have to handle the corner cases when a[i] != a[j] so the answer is: 

    `ans = max(start[a[i]] + cnt[a[i]] - i, j-start[a[j]], QUERY(a[i]+1, a[j]-1))`

    So you have to keep track of the counter and the first appearance of every value.

    → Reply
»
9 years ago, # |
  Vote: I like it +25 Vote: I do not like it

For the third problem (online + arbitrary values):

  1. Let's find the most frequent value as well as number of its occurrences.
  2. Let's suppose that we can get amount of occurrences of number X in segment [L, R] in . Can be done with map from value to list of positions + binary search. Or, what is better, compress all numbers in the array first and then use array instead of map. We will use that we have small numbers only in the future.
  3. Observation: if we know answer for segment [L, R] (say, it's value X), then the most frequent value for segment [L', R'] (where L' ≤ L ≤ R ≤ R') is either X or it lies in .
  4. That is, if we know answer for [L, R] we can find answer for [L', R'] in by combining previous points.

Next idea is sqrt decomposition. For a fixed L we can calculate answers for all possible Rs in O(N) (just keeping current amount of occurrences for each number in an array). Unfortunately, we cannot precalculate answers for all segments (it would be O(N2), to let's do it for K uniformly distributed Ls, it will be O(NK).

Then, we have some queries incoming. Suppose we have query [L, R]. Then we know that we can "shift" L for not more than elements and get a precalculated query. With the power of point 3 we now can answer query in .

The only thing left is to chose K wisely. We can let and have precalc and per query. Or we can minimize , where Q is amount of queries, and it's minimal when (just take a derivative). That way we have for precalculation and per query. When N ≈ Q we have for precalc and per query, which sums up to

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

Auto comment: topic has been updated by Mhammad1 (previous revision, new revision, compare).

→ Reply