Author - Sweta Seth
Tester - Abhisekh Paul, Sayan Poddar
Editorialist - Sweta Seth
Difficulty - Easy
Problem:
In the problem, it is required to find the sum of numbers in an array from l to r.
Explanation:
The optimized code will take O(n) time.
You can do this by using a prefix array where you can store the sum of elements from 0-1, 0-2, 0-3…so on.
Time Complexity:
O(n)
Solution:
C++:
Setter’s Solution
#include <bits/stdc++.h>
using namespace std;
#define F(i,a,b,c) for(int i=a;i<b;i+=c)
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int t;
cin >> t;
while(t--){
int n,q;
cin>>n>>q;
vector<long long> v(n);
F(i,0,n,1)
cin>>v[i];
vector<long long> pref(n);
pref[0] = v[0];
for(int i=1;i<n;i++)
pref[i] = pref[i-1] + v[i];
int l,r;
for(int i=0;i<q;i++){
cin>>l>>r;
--l;--r;
long long ans;
if(l == 0){
ans = pref[r];
}
else{
ans = pref[r] - pref[l-1];
}
cout<<ans<<'\n';
}
}
}
Java:
Tester’s Solution (Abhisekh Paul)
//package myplace;
import java.util.*;
import java.io.*;
class ecjnov1 {
public static void main (String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
// Scanner sc=new Scanner(System.in);
int t=Integer.parseInt(br.readLine());
while(t>0)
{
String s[]=br.readLine().split(" ");
int n=Integer.parseInt(s[0]);
int q=Integer.parseInt(s[1]);
String s1[]=br.readLine().split(" ");
int a[]=new int[n];
for(int i=0;i<n;i++)
{
a[i]=Integer.parseInt(s1[i]);
}
int p[]=new int[n];
p[0]=a[0];
for(int i=1;i<n;i++)
{
p[i]=a[i]+p[i-1];
}
for(int i=0;i<q;i++)
{
String s2[]=br.readLine().split(" ");
int a1=Integer.parseInt(s2[0]);
int a2=Integer.parseInt(s2[1]);
int sum=0;
a1--;
a2--;
if(a1==0)
{
sum=p[a2];
}else
{
sum=p[a2]-p[a1-1];
}
System.out.println(sum);
}
t--;
}
}
}
Python:
Tester’s Solution (Sayan Poddar)
for _ in range(int(input())):
n,q= list(map(int, input().split()))
a=list(map(int,input().split()))
b=[0]
c=0
for i in range(n):
c=c+a[i]
b.append(c)
for _ in range(q):
l,r= list(map(int, input().split()))
print(b[r]-b[l-1])