Algorithm

To calculate the prefix sum array for any given array, we create a prefix array of the same size and initialize the first element of prefix sum array to the array[0]. Because for the first element, the sum of elements up to 0 is the 0th element itself.

For every consecutive index, to calculate the value of prefix sum of that index, we simply add the original array element of that index with the prefix sum of previous index. This is because prefix sum of previous index stores the sum of all the elements upto previous index.

Prefix Sum technique is used in a lot of problems such as Equilibrium Index, Range Sum Queries, Subarrays with Sum K and many more.

Code

#include <bits/stdc++.h>
using namespace std;

// Solution class
class Solution {
public:
    // Function to compute prefix sum array
    vector<int> computePrefixSum(vector<int>& nums) {
        // Create prefix sum array of same size
        vector<int> prefix(nums.size(), 0);

        // Set first element
        prefix[0] = nums[0];

        // Compute prefix sum iteratively
        for (int i = 1; i < nums.size(); i++) {
            prefix[i] = prefix[i - 1] + nums[i];
        }

        // Return the prefix sum array
        return prefix;
    }
};

// Main function
int main() {
    // Input array
    vector<int> nums = {1, 2, 3, 4, 5};

    // Create Solution object
    Solution sol;

    // Call function
    vector<int> 