sandeepandey's blog

Segment Tree
By sandeepandey, 11 years ago, In English

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.

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

Comments Comments (10)
| Write comment?
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Please give me idea ?

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

    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 :)

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

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.

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

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

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

      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]

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

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

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

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

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

          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)

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

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.

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

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.

→ Reply