finding the sum of smaller elements on left

4
votes

i came across a problem of finding the number of smaller elements on left of each element in an array of integers, which can be solved in O(nlgn) by using Binary Indexed trees(like AVL, etc) or Merge Sort. Using an AVL tree one can calculate the size of left sub-tree for each element and this would be the required answer. However I can't come up how to calculate the sum of the smaller elements left to each element efficiently. For each element , do i have to traverse the left sub-tree and sum the values at nodes or is there any better way(using Merge Sort etc)? E.g for the array: 4,7,1,3,2 the required ans would be: 0,4,0,1,1

Thanks.

3
algorithmdata-structures
Shouldn't the last answer be 1 too? Also, could you describe how would you solve the counting problem using an AVL tree? It's not clear to me. - svick
thanks..corrected.For counting problem,while adding any element it is compared to root ,if less then add to left else to right. So for any node the size of its left sub-tree would give the number of elements smaller than it. - pranay
Yes, that way you can count the number of items smaller than it. But they won't be limited to the items on the left of it. Oh, maybe now I get it: you count the smaller items right after you insert something, not at the end, right? - svick

3 Answers

2
votes

In Binary Indexed trees you store the number of child nodes for every node of the binary search tree. This allows you to find number of nodes, preceding each node (number of smaller elements).

For this task, you can store the sum of child node values for every node of the binary search tree. This allows you to find the sum of values for preceding nodes (sum of smaller elements). Also in O(n*log(n)).

2
votes

Check this tutorial on Binary Indexed Tree. This is a structure, that uses O(n) memory and can proceed such tasks:
1. Change value of a[i] by(to) x, call this add(i,x);
2. Return sum all of a[i], i<=m, call this get(x).
in O(log n).

Now, how to use this to your task. You can do this in 2 steps. Step one. Copy, sort and remove duplicates from original array. Now you can remap numbers, so they are in range [1...n].
Step 2. Now walk through the array from left to right. Let A[i] - be the value in original array, new[i] - mapped value. (if A = [2, 7, 11, -3, 7] then new = [2, 3, 4, 1, 2]).

The answer is get(new[i]-1).

Update the values: add(new[i], 1) for counting, add(new[i], A[i]) for sum.

All in all. Sorting and remapping is O(n logn). Working on array is n * O(log n) = O(n log n). So total complexity is O(n logn)

Alternatively, use treap (in russian).

EDIT: Building new array.
Suppose the original array A = [2, 7, 11,-3, 7]
Copy it to B and sort, B = [-3, 2, 7, 7, 11]
Do a unique B = [-3, 2, 7, 11].
Now to get new, you can

  1. add all of elements to map in increasing order, e.g. (-3 -> 1, 2->2, 7->3, 11->4)
  2. for each element in A, do a binary search over B
1
votes

The following code has a complexity of O(nlogn). It uses a binary indexed tree to solve the problem. 

#include <cstdio>
using namespace std;

const int MX_RANGE = 100000, MX_SIZE  = 100000;
int tree[MX_RANGE] = {0}, a[MX_SIZE];

int main() {
  int n, mn = MX_RANGE, shift = 0;
  scanf("%d", &n);

  for(int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    if(a[i] < mn) mn = a[i];  
  }

  shift = 1-mn; // we need to remap all values to start from 1

  for(int i = 0; i < n; i++) {
    // Read answer
    int sum = 0, idx = a[i]+shift-1;
    while(idx>0) {
      sum += tree[idx];
      idx -= (idx&-idx);
    } 

    printf("%d ", sum);

    // Update tree
    idx = a[i]+shift;
    while(idx<=MX_RANGE) {
      tree[idx] += a[i];
      idx += (idx&-idx);
    }
  }

  printf("\n");
}