title: How to use Binary Indexed tree to count the number of elements that is smaller than the value at index?
body: <p>The problem is to count the number of of values less than the value after index. Here is the code, but I can't understand how binary indexed tree has been used to do this?</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;vector&gt;
  #include &lt;algorithm&gt;
  #define LL long long
  #define MOD 1000000007
  #define MAXN 10
  using namespace std;
  typedef pair&lt;int, int&gt; ii;
  int BIT[MAXN+1];
  int a[MAXN+1];
  vector&lt; ii &gt; temp;
  int countSmallerRight[MAXN+1];
  int read(int idx) {
      int sum = 0;
      while (idx &gt; 0) {
      sum += BIT[idx];
      idx -= (idx &amp; -idx);
      }
      return sum;
  }
  void update(int idx, int val) {
      while (idx &lt;= MAXN) {
      BIT[idx] += val;
      idx += (idx &amp; -idx);
      }
  }
  int main(int argc, const char * argv[])
  {
  int N;
  
  scanf("%d", &amp;N);
  
   for (int i = 1; i &lt;= N; i++) {
      scanf("%d", &amp;a[i]);
      temp.push_back(ii(a[i], i));
      }
  
  sort(temp.begin(), temp.end());
  countSmallerRight[temp[0].second] = 0;
  update(1, 1);
  update(temp[0].second, -1);
  
  for (int i = 1; i &lt; N; i++) {
      countSmallerRight[temp[i].second] = read(temp[i].second);
      update(1, 1);
      update(temp[i].second, -1);
  }
  for (int i = 1; i &lt;= N; i++) {
      printf("%d,", countSmallerRight[i]);
  }
  
  
  putchar('\n');
  
  
  return 0;
  
  
  }
  </code></pre>
  
  <p>It would be helpful if someone could explain the working principal of the code.</p>