Range Sum Query

Problem: Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive. Implement the NumArray class:

1. NumArray(int[] nums) Initializes the object with the integer array nums.
2. int sumRange(int i, int j) Return the sum of the elements of the nums array in the range [i, j] inclusive (i.e., sum(nums[i], nums[i + 1], ... , nums[j]))

Example:

Input
Array = [1, 2, 3, 4]
SumRange(1, 2)
SumRange(1, 3)
Output
5
9
Explanation
NumArray numArray = new NumArray([1, 2, 3, 4]);
numArray.SumRange(1, 2); // return 5 (2 + 3)
numArray.SumRange(1, 3); // return 9 (2 + 3 + 4) 

Approach: We can save the input array as it is and then whenever SumRange method is called. We can do the following:

• sum = 0
• For itr = i To j
• sum += array[itr]
• return sum

But then each SumRange call will take O(n) time. Let's see how we can make it better; Instead of saving the input array as it is what we can do is we can save the cumulative sum. That means we can have a array say "Sums" where Sums[i] will contain the cumulative sum of elements from [0...i] of input array:

Sums[i] = arr[0] + arr[1] + arr[2] + ... + arr[i]

Once we saved this array. SumRange(i, j) will be very simple to implement:

• IF i == 0 THEN return Sums[j]
• ELSE return Sums[j] - Sums[i - 1]

That's it!

Implementation in C#:

    public class NumArray

    {

        public NumArray(int[] nums)

        {

            if (nums?.Length > 0)

            {

                this.sums = new int[nums.Length];

                if (nums.Length > 0)

                    this.sums[0] = nums[0];

                for (int i = 1; i < nums.Length; ++i)

                {

                    this.sums[i] = this.sums[i - 1] + nums[i];

                }

            }

        }

        public int SumRange(int i, int j)

        {

            if (this.sums?.Length <= 0)

            {

                return 0;

            }

            return i == 0 ? this.sums[j] : this.sums[j] - this.sums[i - 1];

        }

        private int[] sums;

    }

Complexity: O(n) for constructor and O(1) for SumRange