using System;

// Prefix sum,aka "cumulative sum", is a concept in mathematics and computer science where each element of a sequence is the sum of all preceding elements up to that position.

// relevant because it's been cached. saving Time making it constant instead of linear or worse

​

public class Program

{

    public static void Main()

    {

        int[] nums = new int[]{5, 2, 1, 6, 3, 8};

         PrefixSum prefixSum = new PrefixSum(nums);

         // Example usage:

        Console.WriteLine("Prefix sum of elements up to index 3: " + prefixSum.GetSum(3)); // Output: 10

        Console.WriteLine("Sum of elements from index 1 to index 3: " + prefixSum.GetRangeSum(1, 3)); // Output: 9

    }

}

​

public class PrefixSum

{

    private static int[] _prefixSum;

    public PrefixSum(int[] nums)

    {

        int n = nums.Length;

        _prefixSum = new int[nums.Length + 1]; // +1 in order to allocate all original element count plus the final SUM of all original elements.

        for(int i =1; i <= n; i++)

        {

            _prefixSum[i] = _prefixSum[i-1] + nums[i-1]; 

        }

    }

    public int GetSum(int i)

    {

        if (i < 0 || i >= _prefixSum.Length) // validate for out of range.

        {

            throw new ArgumentOutOfRangeException(i.ToString());

        }

        return _prefixSum[i];

    }

    // Two pointers from index i to j

    public int GetRangeSum(int i, int j)

    {

        if (i < 0 || j >= _prefixSum.Length || i > j) // validate for out of range.

        {

            throw new ArgumentOutOfRangeException();

        }

        return _prefixSum[j + 1] - _prefixSum[i]; // substract the piece to the left to remove any previous addition from the start.

    }

}

​