Sum of previous numbers that are greater than current number for given array

Approach 1 (Naive)

We can solve this problem by finding all the elements on the left side that are greater than the current element and then adding them up.

Algorithm

1. Iterate over all the elements in an array(using index i) and do the following.

i) Iterate over all the previous elements(using index j) and check if this element is strictly greater than the current element.

ii) If Yes, increment ans[i] by arr[j].

2. Print the array ans.

Program

#include <bits/stdc++.h>
using namespace std;
 
// Main function which gives array containing sum of previous
// elements which are greater than the current element.
void solve(vector<int> &v, int n){
    vector<int> ans(n, 0);
 
    // Iterate over all the elements in the array.
    for(int i=0; i<n; i++){
 
        // Iterate over all previous element and
        // those elements which are greater than the current element.
        for(int j=i-1; j>=0; j--){
            if(v[j] > v[i]){
			ans[i] += v[j];
 		}
        }
    }
 
    // Print the answers.
    for(int i=0; i<n; i++) {
		cout << ans[i] << " ";
    }
    cout<<endl;
}
 
// Driver function.
int main(){
    int tt; 
    cin >> tt;
    while(tt--){
        int n; cin >> n;
        vector<int>v(n);
        for(int i=0; i<n; i++) {
		cin >> v[i];
 }
        solve(v, n);
    }
    return 0;
}

INPUT

2
5
2 6 4 1 7
5
7 3 6 2 1

OUTPUT

Sum of prev greater elements are: 0 0 6 12 0
 
Sum of prev greater elements are: 0 7 7 16 18

Time Complexity

The time complexity of the above approach is O( N ² ) since we are fixing two indexes at a time.

Space Complexity

The auxiliary space complexity of the program is O( 1  ). 

Approach 2 (Efficient)

We efficiently solve this problem using Fenwick Tree or Binary Indexed Tree. 

Binary Indexed Tree allows efficient calculation of prefix sum and updates of array elements in O( logN). We can use array elements as indexes in the Binary Indexed Tree. The idea is to calculate the sum of elements that are smaller or equal to the current element and then subtract it from the total sum of previous elements. This will give us the sum of all previous elements that are strictly greater than the current element.

Algorithm

1. Declare an array BIT[] representing Binary Indexed Tree of size maxElement+1 (We are using array elements as index; therefore, we need an array of size maxElement+1).

2. Iterate over all the elements (using index i) and do the following.

i) Calculate the sum of elements that are smaller than or equal to the current element using Binary Indexed Tree and store it in curr_sum (Elements to the left which were smaller than or equal to the current element were already updated in Binary Indexed Tree).

ii) Sum of previous elements which are strictly greater than current elements will total_sum - curr_sum. Print it.

iii) Now update the current element in the Binary Indexed Tree.

iv) Update total_sum ( total_sum += arr[i] ).

Program

#include <bits/stdc++.h>
using namespace std;
 
/*--------------- BINARY INDEXED TREE. //BEGINS -----------*/
vector<int>BIT;
 
/**
 * @brief This is a utility function which calculate
 * the sum of array[0 ... idx] using the BIT data structure.
 *
 * @param idx Index tree node.
 * @return int
 */
int Sum(int idx){
    int _sum = 0;
 
    /* Traversing the ancestors of idx node. */
    while(idx > 0){
        _sum += BIT[idx]; // Add current element in count.
 
        idx -= (idx & -idx); // Move to 'sum' parent node.
    }
    // Return count of smaller element on the right side.
    return _sum;
}
 
/**
 * @brief This function updates a node of Binary Indexed Tree(BIT)
 * at given index 'idx'. Given value 'change' is added to BIT[idx] node
 * and its ancestors.
 *
 * @param idx Index tree node.
 * @param change Effective difference that needs to be updated.
 * @return void
 */
void Update(int idx, int change){
 
    /* Traverse over all ancestors of BIT[idx] and add 'change' */
    while(idx < BIT.size()){    
        BIT[idx] += change; // Add 'change' in current node.
 
        idx += (idx & -idx); // Move to 'update' parent node.
    }
}
/*--------------- BINARY INDEXED TREE. //ENDS   -----------*/
 
// Main function which gives array containing sum of previous
// elements which are greater than the current element.
void solve(vector<int>&a, int n){
    int mxElement = INT_MIN;
    for(int i=0; i<n; i++) {
mxElement = max(mxElement, a[i]);
    }
 
    // Initializing the BIT
    BIT.resize(mxElement+1, 0);
 
    // Iterating over the array to find sum of previous elements
    // which are greater than current element.
    cout << "Sum of prev greater elements are: ";
    int total_sum = 0;
    for(int i=0; i<n; i++){
 
        /* Calculating sum of elements which are smaller or equal
        to current element (which occured previouly). */
        int curr_sum = Sum(a[i]);
 
        cout << total_sum-curr_sum << " ";
 
        /* Updating current in the BIT */
        Update(a[i], a[i]);
 
        /* updating total Sum till current element */
        total_sum += a[i];
    }
    cout << "\n\n";
 
    BIT.clear();
}
 
// Driver Code.
int main(){
    int tt; cin >> tt;
    while(tt--){
        int n; cin >> n;
        vector<int>a(n);
        for(int i=0; i<n; i++)cin >> a[i];
 
        solve(a, n);
    }
    return 0;
}

INPUT

2
5
2 6 4 1 7
5
7 3 6 2 1

OUTPUT

Sum of prev greater elements are: 0 0 6 12 0

Sum of prev greater elements are: 0 7 7 16 18

Time Complexity

The time complexity of update and query in Binary Indexed Tree is O(log(sizeofTree)). Here size of the tree is maxElement of the input array. Therefore time complexity of update and query will be O(log(maxElement)).

The overall time complexity of this approach is O(N * log(maxElement)).

Space Complexity

The auxiliary space complexity of the program is O(maxElement).

FAQs

1. What is Fenwick Tree or Binary Indexed Tree?
   A Fenwick tree or Binary Indexed Tree is a data structure that allows efficient calculations of prefix sums and efficient updates of elements in the array (while retaining tree structure & all its properties). 
    
2. What is the time complexity of insertion and query in a Fenwick Tree or Binary Indexed Tree?
   The time complexity of insertion and deletion in a Binary Indexed Tree containing N elements is O(logN).
    
3. What is the advantage of Fenwick tree over Segment tree?
   The main advantage of the Fenwick tree is that it requires less space, is relatively simple to implement, and has concise code.
    
4. What is the disadvantage of the Fenwick tree over the Segment tree?
   We can only use the Fenwick tree in queries where L=1. Therefore it cannot solve many problems.

Key Takeaways

Do check out a similar question here. 

Cheers if you reached here!! 

This article discussed an intriguing problem using the Fenwick Tree or Binary Indexed Tree. Fenwick Tree-based problems are sometimes simple to implement, but finding an efficient approach remains difficult.

Yet learning never stops, for there is a lot more to learn and many more problems such as the sum of two arrays, merge K sorted arrays, etc. to solve. So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Learning!!