Ask HN: Help with understanding a solution to a problem on Segment Trees

In preparation for interviews, I participated in the Accel Hack2 on Hacker Rank. I was able to solve problem number 5 (Devu's Diet), my solution was not within the time limit.

I looked at other people's solutions and learned about Segment trees.

The problem amounts to this:

You are going to build an array of numbers of size N (they could be +ve or -ve). You need to find all possible intervals L, R in 1 to N where sum L, R >= 0.

My solution was this:

  //helper function
  long the_sum(int i, int j, long sum_asc[], long sum_dsc[], long diff[], int N) {
      if (i == j) {
          return diff[i];
      }
      else if (i == 0 && j == N-1) {
          return sum_asc[N-1];
      } else if (i == 0 && j != N-1) {
          return sum_asc[j];
      } else if (i != 0 && j == N-1) {
          return sum_dsc[i];
      } else {
          return sum_asc[j] - sum_asc[i-1] ; 
      }
  }


  // main Algo
  array[] -> initialised to data
  sum_asc[] -> initialised to sum ascending 
  sum_dsc[] -> initialised to sum descending

  count = 0;
  for (i = 0 to N-1)
     for (j = i to N-1)
         long sum =  the_sum(i, j, sum_asc, sum_dsc, array, N);
         if (sum >= 0) {
              ++ count;
         }

There are 4 classes of solutions that passed.

     1. Using Binary Indexed Trees
     2. Using Segment Trees
     3. Using Mergesort and counting the inversions done
     4. Using an AVL (any other balanced tree would have done)
 
     All solutions in these classes were within the time limit.

If anyone can throw some light on how a Segment tree could be applied to the solution, or how any other solutions worked would be great. I am able to understand how a segment tree can work to calculate a sum from L to R (in array 1 to N). What Im not able to understand is how to apply it to work for all L,R intervals in 1 to N; there is some key insight that I'm missing.

Thanks in advance.