Блог пользователя sandeepandey

Автор sandeepandey, 11 лет назад, По-английски

Count smaller elements on right side

input :[4,12,5,6,1,34,3,2] output: [3,5,3,3,0,2,1,0]

I know this can be solved using MergeSort but i want to know how to solve it using segment tree ? What actually we have to store in Node of segment tree.

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Please give me idea ?

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    store numbers in pair of (value, index) then sort them. then start from the smaller one and for each one count number of element in array that you have visit them (they have smaller value) and their index is bigger than this one. then add 1 to index of this one in segment tree.

    I hope this could help you and sorry for my poor English :)

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

start from the right, when we encounter element x, the answer is query from [0..x-1], then update the segment tree by increasing value on index x by 1 on the segment tree.

this is similar to counting sort, if the maximum element is too large, just compress the data first.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Right :) got. Thanks :) What so you mean compress data first ?

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      If values are big enough (up to 10^9 or even 10^18) you can't usually just create RSQ structure. You should make numbers smaller without changing its order. For example [5,7,5,100000] -> [0,1,0,2]

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        And How it is coming ? [5,7,5,100000] -> [0,1,0,2] ?

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          basically change the value of the smallest number in the current data to 0, 2nd smallest to 1, 3rd smallest to 2, etc

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          zeulb explains the idea what to do. I'd recommend you to think how to do that yourself. It could be easily done in nlogn. Hints:

          You may use std::set/java.util.TreeSet or sort,unique and binary search. (The second is faster)

»
11 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

You can use Binary Indexed Tree. Here is a code.

void update(int i) { for(; i < maxNumber; i += i&-i) BIT[i]++; }

int find(int i) { int res(0); for(; i; i -= i&-i) res += BIT[i]; return res; }

void solve() { read(A); for(i = N; i >= 1; i--) { r[i] = find(A[i]); update(A[i]); } } You can update BIT( Binary Indexed Tree ) int O(logN) and get the result in O(logN). Then complexity is O(NlogN) but it is faster than segment tree and you can implement this easier.

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

We can solve this problem by using BIT and Segment Tree (of course). The condination is the values must be smaller than 10000000 and strictly larger than 0 (if not, you can compress your array by replace value of array with rank of it in array, for example, [500,700,500,850] -> [1,2,1,3]). In our segment tree, node k whick manage segment [l,r] will contains sum of elements from l to r. Let i run from n down to 1, with i, we assign result[i] := segmenttree.get(1,a[i]-1), then call segmenttree.set(a[i], 1) (increase element a[i]-th in tree by 1). Lastly, we print array result[].

This is pseudo code which I hope it can help you:

declare tr : SegmentTree;
:::
for i = n downto 1
    rslt[i]=tr.get(1, a[i]-1);
    tr.set(a[i], 1);

print result[]

It is easier when you use Binary Indexed Tree.