SPOJ "It's a murder!" challenge

I wrote a solution for SPOJ "It's a murder!". I'm exceeding the time limit even after n log(n) solution and fast I/O.

Given a list of numbers, I need to calculate the sum of the sum of the previously encountered numbers that are smaller than the current number. For example, given 1 5 3 6 4, the answer is

(0) + (1) + (1) + (1 + 5 + 3) + (1 + 3) = 15

My code has complexity n log(n) and is pretty much similar to how we calculate the number of inversions. The function merge in the code below merges two sorted arrays and the function merge_sort is the basic call to merge sort procedure. The array sum1 stores the cumulative sum in array1 of elements whose index is strictly less less that current index . The variable ans stores the final answer. How can I make my code more efficient ?

```
#include
using namespace std ;

//Declaration of global variables
int array[100000] , array1[100000] , array2[100000] ;
long long int sum1[100000] ;
long long int ans ;

void merge_sort(int left , int right) ;
void merge(int left , int mid , int right) ;

int main()
{
int t,counter,n,i ;

// t is the number of testcases
scanf("%d",&t) ;

for(counter=0;counter=array2[index2])
{
ans = ans + sum1[index1];
array[index] = array2[index2] ;
index++ ;
index2++ ;
}

}

if(index1<mid-left+1)
{
while(index1<mid-left+1)
{
array[index] = array1[index1] ;
index++ ;
index1++ ;
}
}
else if(index2<right-mid)
{
while(index2<right-mid)
{
ans = ans + sum1[index1-1] + array1[index1-1];
array[index] = array2[index2] ;
index++ ;
index2++ ;
}
}
}

void merge_sort(int left , int right)
{
// Typical merge sort procedure
if(left==right)
{

}
else
{
int mid = (left+right)/2 ;
merge_sort(left , mid) ;
merge

Your main issue is this line:

memset(sum1,0,sizeof(sum1)) ;

The whole array is being initialized to zero, even if you are only dealing with a range of one element. You really only need to initialize the first element:

sum1[0] = 0; // initialize here

// copying into array1 from left to mid 
index1 = 0 ;
for(index=left;index<mid+1;index++)
{
    if(index1!=0)
    {
        sum1[index1] = sum1[index1-1] + array1[index1-1] ;
    }

The rest is already assigned proper values.

StackExchange Code Review Q#133779, answer score: 2