Agenda
Range queries
Pre x sum
Sum of even/odd indices
Special index
Total add space 56 4N
S C OINI
Reversing the array
Rotate the array K times
< Question > : Given an array of N integers and Q queries. For each query calculate the
sum of elements in the range - [ L , R ]
Note : L and R are indices such that L ≤ R. 1 ≤ N, Q ≤ 10^5
-10^9 <= A[i] <= 10^9
0 1 2 3 4 5 6 7 8 9
arr 10 3 6 2 4 5 2 8 9 3 1
9
10
12
14
9
BruteForceApproach Q size of
Queries arr
void Querysum int Queries IE intarre
N size of
For i o is Queries length Itt arr
e Queriestisco
ter sumIY.my
a Queries cities
0 0
1 0 N
For j e jersj.tt N
2 0 N
sum arr j l
i
print sum Q 10 N N
y Total Iter
tim
N Q
TC O N Q
705 105
S C 011
10108
YLE
• Given Royal Challengers Bengaluru's cricket scores for rst 10 overs of batting.
• Runs scored in 7th over = Runs scored till 7ᵗʰ in 6ᵗʰone
aug Eugs sagged
• Runs scored from 6 - 10th over =
Runsscored till 10thover Runs scored till 50ᵗʰer
97 31 66
• Runs scored in 10th over = score 10 score 93 97 88 9
• Runs scored from 3 - 6th over = score 6 score 23
49 8 41
• Runs scored from 4 - 9th over = Score 9 score 3
88 14 74
• Runs scored in lth - rth over = score r score e 1
Observations
Here in case of cricket scoreboard we are having
cumulative sum prefix sum b'coz of which queries can be
answered in const time
How to create psum()
psumei Sum till ith index
OR
sum of elements From 0th till ith index
0 1 2 3 4 0 2 3 4 5
1
arr 2 5 1 7 1 arr 10 32 6 12 20 1
0 1 2 3 4 0 1 2 3 4 5
PSUME 2 7 6 13 14 PSUME 10 42 48 60 80 81
BruteForce Approach
psumen
for i o is N it 1
int sum 0 Toc OINY
5C 0 1
For j 0 j i 1 1
sum arrejs
PSUMEET sum
y
Observations
psumto arr 0
psum I 98210 arr 1
psumto arr 1
psum 2 arr 0 arr 13 arr 23
PSUM I arr 2
psum 3 aro 0 arr 17 arr 27 90613
PSUM 2 98213
psumeis psum i 1 arati i so
Optimised Code
PSUMINI
psum O arr 0
Forli 1 i N it 7
psumci psumei 1 arr i
Y
TC OINI
S C 0111
How to answer the queries ?
3 3 5 9 14 16 24 15 18 19
psum 8 psum 3 18 9 9
pSUM 7 psum 2 15 5 10
psum 33 psum 0 9 3 12
pSUM 4 14
psum 7 psum 6 15 24 9
Generalised eq to Find Prefix sum
sum L R psum R psum L 13 1 0
IF 4 501 Sum L R PSUMER
void Querysum int Queries IE intarre 3
1 Create psume
longpsumIN
psum o arr 0
Forli 1 is N it N iterations
psumci psum i 1 arr i
11 Answer Queries
For 11 0 in Queries 1 1 Q iterations
length
l Queries I 03
a Queries i I
if e 0
sum psumer
else
e 135
sum psumer psum
print sums T C OIN Q1
5C OIN
Range OF Int 2 109 2 109
Range OF Long 9 1018 9 1018
< Question > : Given an arr[N] and Q queries with start(s) and end(e) index. For every query
print sum of all even indexed elements from s to e.
1 ≤ N, Q ≤ 10^5
0 <= s, e <= N
BruteForceApproach
For i o i Queries length Itt
l Queriescisco
a Queries i 1
sum 0 TC OIN Q
Soc 0111
For j e j as jet
sim airess
print sum
Optimisation
Range Queries Prefix Sum
Psum is sum of even index elements from index 0 till ithinde
1 2 3 5
a
psume 2 2 3 3 7 7
Psum is psumli 13 aroli i is even
Psumei psumti 1 i is odd
0 1 2 3 4
are 2 4 3 1 5
0 1 2 3 4
psumi 2 2 5 5 10
Pseudocode
11 create psume
psumIN T C OIN Q1
psumco arr 03 S C OINI
For li 1 I N it 1
if 1 010 2 01
psumei psumei 1 araci
else
psumei psumei 13
11 Answer the Queries
For 11 0 is Queries length it
5 Queries it 0
e Queries i 11
if s 0
sum psumle
sum psumtes psumes 135
print sum
< Question > : For all the queries, nd the sum of odd indexed elements from s to e.
H
Special Index
< Question > : Given an arr[N], count the number of special indices in the array.
Special Index : Index after removing which,
Sum of even indexed elements = sum of odd indexed elements.
constraints
N 105
105 ACI 105
0 1 2 3 4 5 Sum ofelementsof arr 109
arr[ ] [ 4 3 2 7 6 -2 ]
Se so
8 8
9 8
9 9
4 9X
4 10
12 10 X
ans 2
Quiz
1. What will be the sum of elements at ODD indices in the resulting
array after removal of index 2 ?
4 1 7 10 ans 11
What will be the sum of elements at ODD indices in the
2.
resulting array after removal of index 3 ?
0 1 2 3 4 5 6 7 8
2 3 1 0 1 2 2 10 8
ans 15
3. What will be the sum of elements at EVEN indices in the
resulting array after removal of index 3 ?
0 1 2 3 4 5 6 7 8
2 3 1 0 1 2 2 10 8
ans 8
[ BF Idea ] -
For every index i remove element at ith index create new
array from Remaining elements
calculate sum of
evey index elements sum
of odd index elements
If Se So Increment count
count 05
For i 0 NT
11 Create new array after removing element at ith index
CPE
For j o N 1
if j 0102 0
Se Cplj
else
go Cp j is
ifisec.int t
return counts
TC 0 N2
SC OIN
[Optimised Approach ]
0 1 2 3 4 5 6 7 8 9
9821 3 2 6 8 2 9 7 6 4 12
Even Odd
0 1 2 3 4
I 5 6
Odd
7 8
Even
Cpl 3 2 6 8 9 7 6 4 12
sum of Even
Siefelements index elements Sia lemees
after removing 879inforiginal
4th index B Indefrigina
array array
sum of ODD Side imines
index elements L iines
From index
after removing from index 5 9 in
4th index 0 3 in original original
array array
Generalising
O N 1
After Removing ith index
Se i 1 N
Sum
even indices
0
Sumanindiceglitt
So Sum 0 1 1 sumevenindices.li 1 N 1
odd indices
We can Precompute Psum even Psumodd
Psumeventis
SYME IT Ia
mentsfro PsumoaaCi3 ments from
SYMaexf 129
Se i 1 N 1
sum
even indices
0
Sumanindiceglitt
Psumeventi I
PEEN 1Psum.li
So Sum 0 1 1 sumevenindices.li 1 N 1
odd indices
Psumodal 13 Psumeehesumevent.is
Valid only For i so
IF i 0 No elements before ith index
N 1
Se Sumoadindicestitt
Psumodd N 1 Psumoda 0
So sumevenindices.li 1 N 1
PsumeventN 1 Psume en 0
int Special Index int arr int n
1 Create Psumeven Psumodal
11 Check For Special Index
int count 05
For i 0 is n 1 1
if i 0
Psumodd O Psumeven.IN 13 Psumeyento
if Psum oaa N 1
count
else
Se Psum even i 1 Psumodd N 1 Psumodali
So Psumodd 1 1 PsumeventN 1 Psume en i
iflseEÉu 5
3 T C OINI
3 S C O NI
return count
Y
