Prefix Sum

PHOTO EMBED

Wed Aug 17 2022 20:15:27 GMT+0000 (Coordinated Universal Time)

Saved by @Aly #c++ #rangequiries

//prefix Sum 
void pSum(ll a[], ll n, ll pSum[]) {
    pSum[0] = 0;
    for (int i = 0; i < n; i++)
        pSum[i + 1] = pSum[i] + a[i];

}//Time Complexity: O(n)

int main() {
    int n;
    cin >> n;
    ll a[n], p[n + 1];

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
  
    pSum(a, n, p);
}
---------------------------------------------------------------------------------------------------
 //to sum part of array 
 //1- choose left index (L) and right (R); 
 //2- use prefix Sum array
 prefix[R]−prefix[L−1] //prefixSum(L-1 --> R) if array based 1
prefix[R]−prefix[L] //prefixSum(L --> R)  if orginal array based 0
---------------------------------------------------------------------------------------------------  
content_copyCOPY