title: Finding sub-array sum in an integer array
body: <p>Given an array of N positive integers. It can have <code>n*(n+1)/2</code> sub-arrays including single element sub-arrays. Each sub-array has a sum <code>S</code>. Find <code>S's</code> for all sub-arrays is obviously <code>O(n^2)</code> as number of sub-arrays are <code>O(n^2)</code>. Many sums <code>S's</code> may be repeated also. Is there any way to find count of all distinct sum (not the exact values of sums but only count) in <code>O(n logn)</code>.</p>
  
  <p>I tried an approach but stuck on the way. I iterated the array from index 1 to n.<br>
  Say <code>a[i]</code> is the given array. For each index <code>i</code>, <code>a[i]</code> will add to all the sums in which <code>a[i-1]</code> is involved and will include itself also as individual element. But duplicate will emerge if among sums in which <code>a[i-1]</code> is involved, the difference of two sums is <code>a[i]</code>. I mean that, say sums <code>Sp</code> and <code>Sq</code> end up at <code>a[i-1]</code> and difference of both is <code>a[i]</code>. Then <code>Sp + a[i]</code> equals <code>Sq</code>, giving <code>Sq</code> as a duplicate.</p>
  
  <p>Say <code>C[i]</code> is count of the distinct sums in which end up at <code>a[i]</code>.<br>
  So <code>C[i] = C[i-1] + 1 - numbers of pairs of sums in which a[i-1] is involved whose difference is a[i]</code>.</p>
  
  <p>But problem is to find the part of number of pairs in <code>O(log n)</code>. Please give me some hint about this or if I am on wrong way and completely different approach is required problem point that out.</p>