Day 1 :Introduction on Prefix Sum Array

A prefix sum array is another array prefixSum[] of the same size, such that the value of prefixSum[0] = 0,

prefixSum[1] = prefixSum[0]+ arr[0],

prefixSum[2] = prefixSum[1]+arr[1],

prefixSum[3] = prefixSum[2]+arr[2].…….

class Solution {
    public int[] runningSum(int[] nums) {
        int[] prefixSum = new int[nums.length+1];
        for(int i = 0;i<nums.length;i++){
            prefixSum[i+1] = prefixSum[i]+nums[i];
        }
        return prefixSum;
    }
}

Question1: https://leetcode.com/problems/range-sum-query-immutable

Solution: This is basically prefixSum[right] — prefixSum[left-1];

This is a O(1) way to find sum of subarray between two index.

class NumArray {
    int[] ans;

    public NumArray(int[] nums) {
        ans = new int[nums.length+1];
        for(int i = 0;i<nums.length;i++){
            ans[i+1] = ans[i]+nums[i];
        }
    }
    
    public int sumRange(int left, int right) {
            return ans[right+1] - ans[left];
    }
}