# Prefix Sum
---
title: Given N elements and Q queries. For each query, calculate sum of all elements from L to R [0 based index].
description: Sum within a Range
duration: 1800
card_type: cue_card
---

## Problem Description

Given N elements and Q queries. For each query, calculate sum of all elements from L to R [0 based index].

### Example:

A[ ] = [-3, 6, 2, 4, 5, 2, 8, -9, 3, 1]

Queries (Q)

| L | R | Solution |
| -------- | -------- | -------- |
| 4 | 8 | 9 |
| 3 | 7 | 10 |
| 1 | 3 | 12 |
| 0 | 4 | 14 |
| 7 | 7 | -9 |

## Brute Force Approach

For each query Q, we iterate and calculate the sum of elements from index L to R

### Pseudocode

Function querySum(Queries[][],Array[],querySize,size){
     for(i = 0; i < Queries.length; i++){
        L  = Queries[i][0]
        R = Queries[i][1]
        
        sum = 0
        for( j = L ; j <= R ; j++){
           sum += Array[j]
        }
        print(sum)
     }
}

***Time Complexity : O(N * Q)**
**Space Complexity : O(1)***

>Since Time complexity of this approach is O(N * Q) then in a case where there are 10^5 elements & 10^5 queries where each query is (L=0 and R=10^5-1) we would encounter **TLE** hence this approach is Inefficient

---
title: Quiz 1
description:
duration: 60
card_type : quiz_card
---
# Question
Given the scores of the 10 overs of a cricket match
2, 8, 14, 29, 31, 49, 65, 79, 88, 97
How many runs were scored in just 7th over?

# Choices
- [x] 16
- [ ] 20
- [ ] 18
- [ ] 17

---
title: Quiz 1 Solution
description:
duration: 30
card_type: cue_card
---

Total runs scored in over 7th : 65 - 49 = 16
(score[7]-score[6])

---
title: Quiz 2
description:
duration: 45
card_type : quiz_card
---
# Question
Given the scores of the 10 overs of a cricket match
2, 8, 14, 29, 31, 49, 65, 79, 88, 97
How many runs were scored from 6th to 10th over(both included)?

# Choices
- [x] 66
- [ ] 72
- [ ] 68
- [ ] 90

---
title: Quiz 2 Solution
description:
duration: 60
card_type: cue_card
---
Total runs scored in over 6th to 10th : 97 - 31 = 66
(score[10]-score[5])

---
title: Quiz 3
description:
duration: 45
card_type : quiz_card
---
# Question
Given the scores of the 10 overs of a cricket match
2, 8, 14, 29, 31, 49, 65, 79, 88, 97
How many runs were scored in just 10th over?

# Choices

- [ ] 7
- [ ] 8
- [x] 9
- [ ] 10

---
title: Quiz 3 Solution
description:
duration: 60
card_type: cue_card
---
Total runs scored in over 6th to 10th : 97 - 88 = 9
(score[10]-score[9])

---
title: Quiz 4
description:
duration: 45
card_type : quiz_card
---
# Question
Given the scores of the 10 overs of a cricket match
2, 8, 14, 29, 31, 49, 65, 79, 88, 97
How many runs were scored from 3rd to 6th over(both included)?

# Choices

- [ ] 70
- [ ] 40
- [ ] 9
- [x] 41

---
title: Quiz 4 Solution
description:
duration: 60
card_type: cue_card
---
Total runs scored in over 3rd to 6th : 49-8 = 41
(score[6]-score[2])

---
title: Quiz 5
description:
duration: 45
card_type : quiz_card
---
# Question
Given the scores of the 10 overs of a cricket match
2, 8, 14, 29, 31, 49, 65, 79, 88, 97
How many runs were scored from 4th to 9th over(both included)?

# Choices

- [ ] 75
- [ ] 80
- [x] 74
- [ ] 10

---
title: Quiz 5 Solution
description:
duration: 60
card_type: cue_card
---
Total runs scored in over 4th to 9th : 88 - 14 = 74
(score[9]-score[3])

---
title: Observation for Optimised Solution
description:
duration: 1800
card_type: cue_card
---

#### Observation
* On observing cricket board score, we can say that queries can be answered in just constant time since we have cummulative scores.

* In the similar manner, if we have cummulative sum array for the above problem, we should be able to answer it in just constant time.

* We need to create cumulative sum or <B>prefix sum array</B> for above problem.

</div>

---
title: How to create Prefix Sum Array ?
description:
duration: 1800
card_type: cue_card
---

### Definition

pf[i] = sum of all elements from 0 till ith index.

<!-- </div> -->

### Example
Step1:-
Provided the intial array:-
| 2 | 5 | -1 | 7 | 1 |
| --- | --- | --- | --- | --- |

We'll create prefix sum array of size 5 i.e. size equal to intial array.
`Initialise pf[0] = initialArray[0]`

| 2 | - | - | - | - |
| --- | --- | --- | --- | --- |

| 2 | 7 | - | - | - |
| --- | --- | --- | --- | --- |

| 2 | 7 | 6 | - | - |
| --- | --- | --- | --- | --- |

| 2 | 7 | 6 | 13 | - |
| --- | --- | --- | --- | --- |

| 2 | 7 | 6 | 13 | 14 |
| --- | --- | --- | --- | --- |

Finally we have the prefix sum array :-

| 2 | 7 | 6 | 13 | 14 |
| --- | --- | --- | --- | --- |

---
title: Quiz 6
description:
duration: 60
card_type : quiz_card
---
# Question
Calculate the prefix sum array for following array:-

| 10 | 32 | 6 | 12 | 20 | 1 |
| --- | --- | --- | --- | --- |:---:|

# Choices
- [x] `[10,42,48,60,80,81]`
- [ ] `[10,42,49,60,79,81]`
- [ ] `[42,48,60,80,81,10]`
- [ ] `[15,43,58,61,70,82]`

---
title: Brute Force Code to create Prefix Sum Array and observation for Optimisation
description:
duration: 1800
card_type: cue_card
---

pf[N]
for(i = 0; i < N; i++){

    sum = 0;
    
    for(int j=0; j<=i; j++) {
        sum = sum + A[j]
    }
    
    pf[i] = sum;
} 

## Observation for Optimising Prefix Sum array calculations

pf[0] = A[0]
pf[1] = A[0] + A[1]
pf[2] = A[0] + A[1] + A[2]
pf[3] = A[0] + A[1] + A[2] + A[3]
pf[4] = A[0] + A[1] + A[2] + A[3] + A[4]

* Can we observe that we are making redundant calculations?

* We could utilise the previous sum value.
* pf[0] = A[0]
* pf[1] = pf[0] + A[1]
* pf[2] = pf[1] + A[2]
* pf[3] = pf[2] + A[3]
* pf[4] = pf[3] + A[4]

* **Generalised Equation is:** ```pf[i] = pf[i-1] + A[i]```

## Optimised Code:

pf[N]
pf[0] = A[0];
for(i = 1; i < N; i++){
    pf[i] = pf[i-1] + A[i];  
} 

* Time Complexity: O(N)

---
title: How to answer the Queries ?
description:
duration: 1800
card_type: cue_card
---

A[ ] = [-3, 6, 2, 4, 5, 2, 8, -9, 3, 1]

pf[ ] =[-3, 3, 5, 9, 14, 16, 24, 15, 18, 19]

| L | R | Solution | |
| -------- | -------- | -------- | -------- |
| 4 | 8 | pf[8] - pf[3] | 18 - 9 = 9 |
| 3 | 7 | pf[7] - pf[2] |15 - 5 = 10 |
| 1 | 3 | pf[3] - pf[0] |9 - (-3) = 12 |
| 0 | 4 | pf[4] |14 |
| 7 | 7 | pf[7] - pf[6] |15 - 24 = -9 |

## Generalised Equation to find Sum:

sum[L R] = pf[R] - pf[L-1]

Note: if L==0, then sum[L R] = pf[R]

### Complete code for finding sum of queries using Prefix Sum array:

Function querySum(Queries[][],Array[],querySize,size){  
    //calculate pf array
    pf[N]
    pf[0] = A[0];
    for(i = 1; i < N; i++){
        pf[i] = pf[i-1] + A[i];  
    } 
    
    //answer queries
    for( i=0; i<Queries.length; i++){
        L  = Queries[i][0];
        R = Queries[i][1];

        if(L == 0) {
            sum = pf[R]
        }
        else {
            sum = pf[R] - pf[L - 1];
        }
        
        print(sum);
    }
}

***Time Complexity : O(N+Q)**
**Space Complexity : O(N)***

### Space Complexity can be further optimised if you modify the given array.

Function prefixSumArrayInplace(Array[],size){
    for(i = 1; i < size; i++){
        Array[i] = Array[i-1] + Array[i];
    }
}

***Time Complexity : O(N)**
**Space Complexity : O(1)***

---
title: Problem 1 Sum of even indexed elements
description:
duration: 240
card_type: cue_card
---

Given an array of size N and Q queries with start (s) and end (e) index. For every query, return the sum of all **even indexed elements** from **s to e**.

### Example

A[ ] = { 2, 3, 1, 6, 4, 5 }
Query :
 1 3
 2 5
 0 4
 3 3
 
Ans:
 1
 5
 7
 0

### Explanation:
* From index 1 to 3, sum: A[2] = 1
* From index 2 to 5, sum: A[2]+A[4] = 5
* From index 0 to 4, sum: A[0]+A[2]+A[4] = 7
* From index 3 to 3, sum: 0

### Brute Force
How many of you can solve it in $O(N*Q)$ complexity?
**Idea:** For every query, Iterate over the array and generate the answer.

---
title: Problem 1 Observation for Optimisation
description: Observation for Optimisation
duration: 240
card_type: cue_card
---

Whenever range sum query is present, we should think in direction of **Prefix Sum**.

**Hint 1:** Should we find prefix sum of entire array?
**Expected:** No, it should be only for even indexed elements.

**We can assume that elements at odd indices are 0 and then create the prefix sum array.**

Consider this example:-

  A[] = 2  3  1  6  4  5
PSe[] = 2  2  3  3  7  7

> Note: PS_e[i] denotes sum of all even indexed elements from 0 to i^th index.

If **i is even** we will use the following equation :-
<div class="alert alert-block alert-warning">
PSe[i] = PSe[i-1] + A[i]
</div>

If **i is odd** we will use the following equation :-
<div class="alert alert-block alert-warning">
PSe[i] = PSe[i-1]
</div>

---
title: Quiz 7
duration: 60
card_type: quiz_card
---

# Question
Construct the Prefix Sum for even indexed elements for the given array
[2, 4, 3, 1, 5]

# Choices
- [ ] 1, 6, 9, 10, 15
- [x] 2, 2, 5, 5, 10
- [ ] 0, 4, 4, 5, 5
- [ ] 0, 4, 7, 8, 8

---
title: Quiz 7 Explanation
description:
duration: 240
card_type: cue_card
---

We will assume elements at odd indices to be 0 and create a prefix sum array taking this assumption.
So ```2 2 5 5 10``` will be the answer.

---
title: Problem 1 Pseudocode
description:
duration: 240
card_type: cue_card
---

void sum_of_even_indexed(int A[], int queries[][], int N){
    // prefix sum for even indexed elements
    int PSe[N]; 
    
    if(A[0] % 2 == 0)PSe[0] = A[0];
    else PSe[0] = 0;
    
    for(int i = 0; i < N; i++){
        if(i % 2 == 0){
            PSe[i] = PSe[i-1] + A[i];
        }
        else {
            PSe[i] = PSe[i-1]; 
        }
    }
    for(int i=0; i < queries.size(); i++) {
        s = queries[i][0]  
        e = queries[i][1]
        if(s == 0){
            print(PSe[e])
        }
        else {
            print(PSe[e]-PSe[s-1])
        }         
            
    }
 
}

### Complexity
-- TC - $O(n)$
-- SC - $O(n)$

---
title: Problem 1 Extension Sum of all odd indexed elements
description: Extension Sum of all odd indexed elements
duration: 240
card_type: cue_card
---

If we have to calculate the sum of all ODD indexed elements from index **s** to **e**, then Prefix Sum array will be created as follows -

> if i is odd
<div class="alert alert-block alert-warning">
PSo[i] = PSo[i-1] + A[i]
</div>

> and if i is even :-
<div class="alert alert-block alert-warning">
PSo[i] = PSo[i-1]
</div>

---
title: Next Class Content
description: Topics that'll be taken up in next class
duration: 400
card_type: cue_card
---

In next session, we'll learn 2 things -

**1. Carry Forwards Technique**
* In the context of Data Structures and Algorithms (DSA), the carry-forward technique is like a magic wand that helps us utilize the previously calculated results.
* It's a clever way of solving problems so that we don't have to recalculate the same results repeatedly, thus optimizing the Time Complexity.

**2. Basics of Subarrays**
* Subarrays are contiguous segments or slices of an array. They play a crucial role in various aspects of computer science, data analysis, and algorithm design.
* Dynamic Programming: Many dynamic programming algorithms use subarrays to build solutions incrementally, leading to efficient solutions for complex problems.
* Efficient Subarray Operations: Many array-related operations like sorting, searching, and updating can be optimized using techniques that rely on subarrays, such as divide-and-conquer algorithms.

Overall, subarrays are a powerful concept that simplifies algorithmic problem-solving and data manipulation.