Number of inversions on a segment

Question

I was trying to do this question and I get TLE on one the test cases (the actual link to the question will ask you to login).

What is an inversion?

An inversion of an element is the number of elements to the left which are greater. Sum of number of numbers throughout a segment is the answer.

It is based on Segment Trees.

My attempt is this:

#include <bits/stdc++.h>
#define ll long long
using namespace std;

struct segtree {

    int size;
    vector<int> sums;

    void init(int n){
        size=1; 
        while(size<n)
            size*=2;
        sums.assign(2*size,0);
    }

    void change(int i,int v,int x,int lx,int rx){
        if(rx-lx==1){sums[x]+=v;return;}
        int m=(lx+rx)/2;
        if(i<m)
            change(i,v,2*x+1,lx,m);
        else
            change(i,v,2*x+2,m,rx);
        sums[x]= sums[2*x+1] + sums[2*x+2];
    }
    void change(int i,int v){
        change(i,v,0,0,size);
    }

    int calc(int l,int r,int x,int lx, int rx){
        if(lx>=l&&rx<=r) return sums[x];
        if(rx<=l||lx>=r) return 0;
        int m =(lx+rx)/2;
        return calc(l,r,2*x+1,lx,m) + calc(l,r,2*x+2,m,rx);
    }
    int calc(int l){
        return calc(l,size,0,0,size);
    }
};

int main(){

    int n, m;
    cin >> n >> m;

    vector<int> a(n);

    for(int i=0;i<n;++i)
        cin >> a[i];

    while(m--) {
        int op;
        cin >> op;

        if(op == 1){

            int x, y;
            cin >> x >> y;

            x-=1;

            segtree st;
            st.init(40);

            int sum = 0;

            for(int i=x;i<y;++i){
                int val = a[i];
                sum += st.calc(val);
                st.change(val-1, 1);
            }

            cout << sum << "\n";

        } else {    
            int x, y;
            cin >> x >> y;
            a[x-1]=y;
        }
    }

    return 0;
}

I wanna know a better time complexity version of the program.

Answer 1

Overall Observations

The function main() is too complex and should be broken up into multiple functions, if you do this you might notice that you are recreating your segtree struct for every query when it only needs to be created once and then each query should be applied to that structure.

Recursion is expensive in terms of resources it might be better to find iterative solutions.

The code is difficult to read and that may be why I am the first person answering.

Avoid using #include <bits/stdc++.h>

The header bits/stdc++.h is not part of the C++ programming standard and includes the whole world, this program needs only 2 C++ headers

#include <iostream>
#include <vector>

I realize that the programming challenge probably provided this for you, but that doesn't mean you should keep it if you know the proper includes.

Avoid using namespace std;

If you are coding professionally you probably should get out of the habit of using the using namespace std; statement. The code will more clearly define where cout and other identifiers are coming from (std::cin, std::cout). As you start using namespaces in your code it is better to identify where each function comes from because there may be function name collisions from different namespaces. The identifiercout you may override within your own classes, and you may override the operator << in your own classes as well. This stack overflow question discusses this in more detail.

Variable Names

While you are using the variable names from the programming challenge, these variables names are not very descriptive and could cause you or someone who might be maintaining this code in a professional environment to make errors in the code.

Horizontal Spacing

One of the standard conventions in programming is to leave a space between an operator and an operand in any statement, this makes the code easier to read, examples:

        if(rx-lx==1){sums[x]+=v;return;}

versus

        if (rx - lx == 1) { sums[x] += v; return; }

        int m=(lx+rx)/2;

versus

        int m = (lx + rx) / 2;

Vertical Spacing

        if(rx-lx==1){sums[x]+=v;return;}
        int m=(lx+rx)/2;

versus

        if (rx - lx == 1)
        {
            sums[x] += v;
            return;
        }

        int m = (lx + rx) / 2;

As mentioned above, it isn't really clear what the variables m, rx and lx are, especially m.

Unused #define

The code contains:

#define ll long long

This is unused in the scope of the program and should be removed. There are at least 2 ways in C++ that don't require #define, one is a typedef and another is a using statement. While macros will continue to be supported in C++ to remain backwards compatible with C, the trend is to not use macros when possible.

##Magic Numbers There are Magic Numbers throughout the program function (40, 2, 1), it might be better to create symbolic constants for them to make the code more readable and easier to maintain. These numbers may be used in many places and being able to change them by editing only one line makes maintenance easier.

Numeric constants in code are sometimes referred to as Magic Numbers, because there is no obvious meaning for them. There is a discussion of this on stackoverflow.

An enum could be used for the query type.