title: Suggestions for optimization of code to pass TLE on SPOJ
body: <p>I'm trying to solve a problem which is something like this:</p>
  
  <p>I'm given n numbers (1&lt;=n&lt;=10^5).I have to write the sum of all numbers on its left which are smaller than the current number and repeat the process for all n numbers.Then I have to find the sum of all previously obtained sum's.(Each number N,0&lt;=N&lt;=10^6).</p>
  
  <p>For example,</p>
  
  <pre><code>1 5 3 6 4
  less1 less5 less3 less6 less4
   (0) + (1) + (1)+(1+5+3)+(1+3)
    0  +  1  +  1  +  9  +  4
  = 15
  </code></pre>
  
  <p>A trivial solution for this problem will be to run two loops and for each of the given number find sum of all the numbers less than that number and finally give the sum of those sum's as output.The time complexity is O(n^2).</p>
  
  <p>I think a better O(nlogn) solution for this problem using Binary Indexed Tree(Fenwick Tree).
  For each number I'll add each of the number in a global array a and perform two obvious operations of BIT.I think the time complexity of this algorithm is O(nlogn) which if true is obviously better than the previous O(n^2).</p>
  
  <p>I have implemented the code in C++.</p>
  
  <pre><code>#include&lt;iostream&gt;
  #include&lt;cstdio&gt;
  
  using namespace std;
  
  #define max 1000001
  
  long int a[max];
  
  void add(long int v,int idx){
  while(idx&lt;max){
      a[idx] += v;
      idx += (idx &amp; -idx);
  }
  }
  
  long int sum(int idx){
  long int s=0;
  while(idx&gt;0){
      s += a[idx];
      idx -= (idx &amp; -idx);
  }
  return s;
   }
  
   int main()
   {
  int t;
  scanf("%d",&amp;t);
  for(int w=0;w&lt;t;w++){
      int n;
      scanf("%d",&amp;n);
  
      for(int i=0;i&lt;max;i++)
          a[i]=0;
  
      int arr[n];
      for(int i=0;i&lt;n;i++)
          scanf("%d",&amp;arr[i]);
  
      long long res=0;
  
      for(int i=0;i&lt;n;i++){
          if(arr[i]!=0){
             add(arr[i],arr[i]);
             res += (sum(arr[i]-1));
                       }  
      }
  
      printf("%lld\n",res);
  }
  
  return 0;
  }
  </code></pre>
  
  <p>I have two questions:</p>
  
  <p>First, am I doing it correct? / Is my logic correct?</p>
  
  <p>Second, if I'm right about the time complexity to be O(nlogn) then why does it run slow? Can you help me with any further optimizations?</p>
  
  <p>Got Accepted with 1.41 seconds.At same time I have updated my finally accepted code.Any suggestion for optimization ?</p>
  
  <p>Based on the comments I tried my own function for faster I/O but still it's not going my way.This is my function for fast I/O :</p>
  
  <pre><code> inline int read(){
  char c=getchar_unlocked();
  int n=0;
  while(!(c&gt;='0' &amp;&amp; c&lt;='9'))
      c=getchar_unlocked();
  
  while(c&gt;='0' &amp;&amp; c&lt;='9'){
      n=n*10 + (c-'0');
      c=getchar_unlocked();   
  }
  return n;
   }
  </code></pre>
  
  <p>This is the link to the problem :</p>
  
  <p><a href="http://www.spoj.pl/problems/DCEPC206/" rel="nofollow">http://www.spoj.pl/problems/DCEPC206/</a> </p>
  
  <p>If there is anyone who is abled to solve it,please let me know.
  Thanks.</p>