Range Sum Problem

                                  Range Sum Query

It is very often that we need to get a range sum of a array in order to do something. So I just want to briefly discuss 4  different ways to get a range sum from a given array.

             Question: the range sum between index i to index j in array A. 

    Approach 1: Adding element from i to j.  

-- Conditions: No specific condition require to use this approach.

-- Pros: It is the first approach that most people will come up with, which is simple and easy to implement. If you just need answer range sum query once, you probably want to do this. 

-- Cons: Obviously, it has very bad time complexity --> O(N). Besides, if we being asked for same range sum query for many times, it will still do the 0(n) job again and again cause it has no memory anywhere. 

   Approach 2: Pre-Process the array get range sum in constant time 

 -- Condition: This approach only works when the value of given array will not being changed, so there is no update in our input. 

 -- Steps :1. From the second position to end of the array, we add previous value into this position. After this step,  the K th position in the array will store the previous [0 , K] sum as its newly updated value.   

               2. Then we can get the range sum i to j, buy A[j] - A[i-1].   ( Note that if (i-1) < 0, then i is equal to 0, which means we just can take A[j] as the range sum. So A[j] - 0, in this case). 

           Here is the Java code for step 1: 

                                                                 for(int i=1 ;i<A.length;i++){

                                                                    A[i] +=A[i-1];

                                                                    }

-- Pros: Step one will take 0(n) time, but after this step we can get any range sum in O(1) time. 

-- Cons: Again, this way only works if we have a static value array, otherwise we need to update the whole table which will take 0(n) time again. 

    Approach 3: Binary Index Tree 

 -- Condition: This approach only works when i equals 0. So we always being asked about the previous sum from 0 to 3, or 0 to 5. But unlike approach 2, Binary Index Tree support updating the value in the array. 

 -- Steps: 1. Create Binary index Tree 

                2. Update value if need

                3. Get previous Sum.    

Here is the screen shoot of a BinaryIndexTree class. 

           
After you have a class like this, you can just call BITree.getSum(j) to the previous (0 - j) sum, or BITree.updateBITree( value, index) to update a value if you need.

-- Pros: The first step creating tree step cost O(n*log(n)) time.  Then the getSum and updateValue only costs O(log(n)) time afterwards.

-- Cons: It will works when the range query is starting from 0 index based, so if i is not 0, this way will not work properly.

  Approach 4: Segment Tree. 

-- Condition: No specific condition require to use this approach.

-- Steps: 1. Create Segment tree
              2. Update value if need
              3. Get range sum
Here is a screen shoot for a Segment tree class:

And how to call it after you create a segment tree class

( Those code are all available in my GitHub repository under  the Adv_DataStructures folder. Here is the Link: https://github.com/yejiangholy?tab=repositories )

 -- Pros: It works both static and updating value of input array, and any possible query value for i , j. Besides the creating tree, get range sum and updating value operation  are all only need O(log(n)) time complexity !

-- Cons: It is the longest implementation compare to previous 3 approaches.


Do not hesitate to leave any comments.

Enjoy Coding :-)
Ye Jiang
11/26/2016