Finding the sum of smaller elements on the left

Question

I ran into the problem of finding the number of smaller elements to the left of each element in an array of integers, which can be solved in O (nlgn) using binary indexed trees (like AVL, etc.) or Merge Sort. Using the AVL tree, you can calculate the size of the left subtree for each element, and this will be the necessary answer. However, I cannot figure out how to efficiently calculate the sum of the smaller elements remaining before each element. For each element, do I need to go through the left subtree and sum the values ​​in the nodes or is there a better way (using Merge Sort, etc.)? For example, for an array: 4,7,1,3,2 required arrays would be: 0,4,0,1,1

Thanks.

Answer 1

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

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

Answer 2

Mark this tutorial in a binary indexed tree. This is a structure that uses O (n) memory and can perform such tasks:
1. Change the value of a [i] to (to) x, name it add(i,x) ;
2. We return the sum of all [i], I <= m, call it get(x) .
in O (log n) .

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

Answer: get (new [i] -1).

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

Generally. Sort and reassign O (n logn) . Working with an array n * O (log n) = O (n log n) . So the total complexity is O (n logn)

Alternatively use treap .

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

• add all items to be displayed in ascending order, for example. (-3 → 1, 2-> 2, 7-> 3, 11-> 4)
• for each element in A, do a binary search on B

Answer 3

The following code has O (nlogn) complexity. To solve the problem, a binary indexed tree is used.

 #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"); }