WhitePaper's blog

How to solve this problem using segment tree?
By WhitePaper, history, 9 years ago, In English

You are given an array of n integers. Using segment tree how can you find for each number how many numbers are smaller than this are exist before that number. For example:

input: (first number is the value of n) 5 1 4 2 5 3

output: 0 1 1 3 2

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Good day to you,

WLOG — we will assume that all numbers are lesser/equal N (as long as this isn't true, we can "normalize" the numbers {with usage of sort or map to fulfill this}).

Now iterate through array from left to right, while having Segment Tree (or easier Fenwick) which can:

  1. Add +1 to sigle element (interval not necessary)

  2. Sum on interval

You firstly use "Sum on interval [0,A[i]-1]"

Secondly "Add +1 to element A[i]"

Why does it work? As you can see — after each element, all elements from its prefix have +1 added on position of its values, so if you query on interval [0,A[i]-1] you will get the sum of all elements with value 0,1,2,...,A[i]-2,A[i]-1

Hope it was at least slightly understandable.

Good Luck & Have Nice Day!

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

Let the array be A. Let 1 <= A[i] <= 10^5. If the numbers can be larger, map them.

Suppose update(i, x) replaces value of i-th leaf node with x in segment tree. query(i, j) returns sums of all elements within [i, j] range.

Now, iterate the array from left to right. Let's work with first element first.

You want to know how many numbers so far are smaller than A[1]. So you just find query(1, A[1] — 1) from segment tree which is 0. Now,A[1] might be smaller than the next numbers. So, do update(A[1], 1).

Now, next number is A[2]. You have inserted all numbers before that in seg tree. You want to know how many of them are smaller than A[2]. You just do query(1, A[2]-1) which will result in 1.

So, the algorithm is like:

for i = 1 to n 
{
ans[i] = query(1, A[i]-1)
update(A[i], 1)  
}

How to make query and update functions? That's actually the very basoc stuff segment tree do, you should study more about seg tree first if you get stuck there.

→ Reply